LeetCode: Lowest Common Ancestor of a Binary Search Tree Solution

Approach

Properties of a BST (grabbed from leetcode.com):

• Left subtree of a node N contains nodes whose values are lesser than or equal to node N's value.
• Right subtree of a node N contains nodes whose values are greater than node N's value.
• Both left and right subtrees are also BSTs.

From that, we see that the way is:

• find the first node (go from root) that satisfy the condition of a BST (left <= target node <= right)
• if 2 given nodes values are greater than the iterated node, go right
• if 2 given nodes values are smaller than the iterated node, go left

Implementation (recursive)

1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val) {
4 *     this.val = val;
5 *     this.left = this.right = null;
6 * }
7 */
8
9/**
10 * @param {TreeNode} root
11 * @param {TreeNode} p
12 * @param {TreeNode} q
13 * @return {TreeNode}
14 */
15var lowestCommonAncestor = function (root, p, q) {
16  if (
17    (root.val >= p.val && root.val <= q.val) ||
18    (root.val <= p.val && root.val >= q.val)
19  ) {
20    return root
21  } else if (root.val > p.val && root.val > q.val) {
22    return lowestCommonAncestor(root.left, p, q)
23  } else if (root.val < p.val && root.val < q.val) {
24    return lowestCommonAncestor(root.right, p, q)
25  }
26}

Implementation (iterative)

1var lowestCommonAncestor = function (root, p, q) {
2  while (root) {
3    if (p.val < root.val && q.val < root.val) {
4      root = root.left
5    } else if (p.val > root.val && q.val > root.val) {
6      root = root.right
7    } else {
8      break
9    }
10  }
11
12  return root
13}

References

Original problem