aloalgoLowest Common Ancestor of a Binary Search Tree
Medium
You are given the root of a Binary Search Tree (BST), along with two integer values, p and q.
Your task is to find the lowest common ancestor (LCA) of the nodes that contain p and q.
You may assume that:
- Both
pandqare guaranteed to exist within the tree. - All node values throughout the BST are unique. Remember that:
- The LCA is defined as the deepest node in the BST that has both
pandqas descendants (a node can be considered a descendant of itself).
Return the node value of the LCA.
Example 1
Inputs
p = 2
q = 8
Output
6
Explanation:
The root of the BST is 6. Value 2 is in the left subtree, and value 8 is in the right subtree. Thus, 6 is the lowest common ancestor.
Example 2
Inputs
p = 2
q = 4
Output
2
Explanation:
The root is 6. Both 2 and 4 are less than 6, so we move to the left child (2). At node 2, value 2 is equal to the node's value, and value 4 is in its right subtree. Therefore, 2 is the lowest common ancestor.
Example 3
Inputs
p = 2
q = 1
Output
2
Explanation:
The root is 2. Value 1 is less than 2, so it's in the left subtree. Node 2 is the common ancestor of itself and 1.
Inputs
p = 2
q = 8
Output
6