# LeetCode: Lowest Common Ancestor of a Binary Search Tree Solution

Recursive approach

## 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)

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**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} root11 * @param {TreeNode} p12 * @param {TreeNode} q13 * @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 root21  } 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.left5    } else if (p.val > root.val && q.val > root.val) {6      root = root.right7    } else {8      break9    }10  }11
12  return root13}```

Original problem

leetcode

tree

## Next Post

LeetCode: Shuffle an Array

Jul 21, 2021

Fisherâ€“Yates shuffle

## Previous Post

LeetCode: Find Peak Element

Jul 14, 2021

Divide and conquer

Search Posts