loading

Lowest Common Ancestor of a Binary Search Tree — Step-by-Step Visualization

mediumLeetCode #235TreeDFSBinary Search TreeBinary Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: 'The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).'

Algorithm Pattern

BST Property Split

Key Idea

In a Binary Search Tree (BST), if `p` and `q` are both smaller than the current node, the LCA must be in the left subtree. If they are both larger, the LCA must be in the right subtree. If one is smaller (or equal) and the other is larger (or equal), then the current node IS the LCA (the split point).

Step-by-Step Approach

  1. Starting at the root, check if both `p.val` and `q.val` are less than `root.val`.
  2. If yes, move to `root.left` and repeat.
  3. Check if both `p.val` and `q.val` are greater than `root.val`.
  4. If yes, move to `root.right` and repeat.
  5. If neither, the current node is the LCA (the paths to `p` and `q` split here).

Common Gotchas

  • LCA can be one of the nodes themselves if one is an ancestor of the other.
  • The BST property makes this much faster O(log n) than a general binary tree LCA O(n).

Related Problems

← All problems