## Lowest Common Ancestor of a Binary Search Tree

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).”_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5For example, the lowest common ancestor (LCA) of nodes

`2`

and`8`

is`6`

. Another example is LCA of nodes`2`

and`4`

is`2`

, since a node can be a descendant of itself according to the LCA definition.

- if p->val > q->val, swap q and p
- if root == null, reutrn null
- if root->val >= p->val && root->val <= q->val return root; //root is the lowest common ancestor
- if root->val < p->val , recursively find in root->right
- else , recursively find in root->left

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ //duplicates in tree? class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(p->val > q->val){ TreeNode * tmp = p; p = q; q = tmp; } return _lowestCommonAncestor(root, p, q); } TreeNode * _lowestCommonAncestor(TreeNode * root, TreeNode * p, TreeNode * q){ if(root == nullptr){ return nullptr; } else if(p->val <= root->val && q->val >= root->val){ return root;//find the common ancestor } else if(p->val > root->val){ return _lowestCommonAncestor(root->right, p, q); } else{ return _lowestCommonAncestor(root->left, p, q); } } };