55. LCA in BST

Given the root node of a binary search tree (BST) and two node values p,q.

Return the lowest common ancestors(LCA) of the two nodes in BST.

Example 1:

Input : root = [5, 3, 6, 2, 4, null, 7] , p = 2, q = 4

Output : [3]

Explanation :

Below is image of the BST

Example 2:

Input : root = [5, 3, 6, 2, 4, null, 7] , p = 2, q = 7

Output : [5]

Explanation :

Below is image of the BST

Now Your Turn!

Pick the correct output for the given input

Input : root = [2, 1, 4, null, null, 3, 6] , p = 1, q = 6

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of Nodes <= 104
  • 1 <= Node.val <= 105
  • All values in BST are unique.
  • The values p and q are always present in the given BST.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution{
public:
TreeNode* lca(TreeNode* root, int p, int q){
//your code goes here
}
};
Test Case

Input:

P
Q
Root
to save your code