Reference: LeetCode EPI 14.4

Difficulty: Easy

## Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

**Note:**

- All of the nodes’ values will be
`unique`

. `p`

and`q`

are different and both values will exist in the BST.

**Example:**

1 | Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 |

## Analysis

**Methods:**

- Recursion
- Start traversing the tree from the root node.
- If both the nodes
`p`

and`q`

are in the right subtree, then continue the search with right subtree. - Same for left subtree.
- If above steps are not true, it means that we have found the node which is common to node
`p`

‘s and`q`

‘s subtrees. **Bad Code:**1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null) {

return null;

}

// branching

if (p.val < root.val && q.val > root.val) {

return root;

}

if (p.val > root.val && q.val < root.val) {

return root;

}

// other cases

if (p.val == root.val || q.val == root.val) {

return (p.val == root.val) ? p : q;

}

if (p.val < root.val && q.val < root.val) {

return lowestCommonAncestor(root.left, p, q);

} else {

return lowestCommonAncestor(root.right, p, q);

}

}

**Better code:**1

2

3

4

5

6

7

8

9

10

11

12public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null) {

return null;

}

if (p.val < root.val && q.val < root.val) {

return lowestCommonAncestor(root.left, p, q);

} else if (p.val > root.val && q.val > root.val) {

return lowestCommonAncestor(root.right, p, q);

} else {

return root;

}

}**Time:**$O(h)$

**Space:**$O(h)$

- Iteration
- Use $O(1)$ space.
1

2

3

4

5

6

7

8

9

10

11

12public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

while (root != null) {

if (p.val < root.val && q.val < root.val) {

root = root.left;

} else if (p.val > root.val && q.val > root.val) {

root = root.right;

} else {

return root;

}

}

return null;

}**Time:**$O(h)$**Space:**$O(1)$

- Use $O(1)$ space.