Skip to main content

< Back to Data Structures and Algorithms

LeetCode 235 · Trees

Lowest Common Ancestor of a Binary Search Tree

The deepest node with both of two nodes beneath it: in a search tree, the first where they fall on different sides.

Step through it

Examples
Edge cases
root
03542p798q6

p = node 2q = node 8

Step 0 of 6

Output

Running… play or step to the end.

The code

/**
 * Definition for a binary tree node.
 * const TreeNode = val => {
 *     this.val = val
 *     this.left = this.right = null
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 const lowestCommonAncestor = (root, p, q) => {
  /* It is assumed that this is a sorted binary tree
     The left is always either less than or equal to the root,
     The right is always either greater than or equal to the root */
  
  // BOTH P and Q are is less than the root
  if (p.val < root.val &&
      q.val < root.val
  ) {
      // Recurse left down the tree
      return lowestCommonAncestor(root.left, p, q)
  }
  
  // BOTH P and Q are greater than the root
  if (p.val > root.val &&
      q.val > root.val
  ) {
      // Recurse right down the tree
      return lowestCommonAncestor(root.right, p, q)
  }
  
  /* We have now found the common ancestor because neither P or Q are BOTH on one side of the tree.
     We get to this scenario when either:
     - P is on one side, and Q is on the other.
     - P or Q are equal to the root, or both.
     - P or Q are equal to the root, and the other is left or right. */
  return root
}

View it on GitHub (opens in a new tab)