SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

Lowest Common Ancestor in a BST Visualizer

If p and q are both smaller than the node, the answer is on the left. Both bigger, on the right. Otherwise they split here (or one of them is this node): this node is the answer.

Start the Lowest Common Ancestor in a BST simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Find the lowest common ancestor of 35 and 45. Start at the root.
  2. At 50. Compare it with 35 and 45.
  3. 35 and 45 are both smaller than 50, so go left.
  4. At 30. Compare it with 35 and 45.
  5. 35 and 45 are both bigger than 30, so go right.
  6. At 40. Compare it with 35 and 45.
  7. 35 and 45 split at 40: one goes left, one goes right. 40 is the lowest common ancestor.

Try it with your own input →

Lowest common ancestor in a BST in Java, Python, C++, C and JavaScript

TreeNode lca(TreeNode root, int p, int q) {
  TreeNode node = root;
  while (node != null) {
    if (p < node.val && q < node.val) node = node.left;
    else if (p > node.val && q > node.val) node = node.right;
    else return node;
  }
  return null;
}
def lca(root, p, q):
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node
    return None
TreeNode* lca(TreeNode* root, int p, int q) {
  TreeNode* node = root;
  while (node) {
    if (p < node->val && q < node->val) node = node->left;
    else if (p > node->val && q > node->val) node = node->right;
    else return node;
  }
  return nullptr;
}
struct TreeNode* lca(struct TreeNode* root, int p, int q) {
  struct TreeNode* node = root;
  while (node != NULL) {
    if (p < node->val && q < node->val) node = node->left;
    else if (p > node->val && q > node->val) node = node->right;
    else return node;
  }
  return NULL;
}
function lca(root, p, q) {
  let node = root;
  while (node !== null) {
    if (p < node.val && q < node.val) node = node.left;
    else if (p > node.val && q > node.val) node = node.right;
    else return node;
  }
  return null;
}

In an interview

LeetCode 235, Lowest Common Ancestor of a BST. For a plain binary tree (236) you need recursion on both sides instead.

Only one path from the root is walked, so it is O(h) time and O(1) space with the loop. Mention that a skewed BST makes h = n.

More trees