Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
1 /**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
13 if(p->val val && q->val val)
14 return lowestCommonAncestor(root->left,p,q);
15 if(p->val > root->val && q->val > root->val)
16 return lowestCommonAncestor(root->right,p,q);
17 return root;
18 }
19 };