Skip to content

Volume ITechnology

4.14.7 — Lowest Common Ancestor of a Binary Search Tree ​

LeetCode 235 · Medium · ★ Blind 75

The problem ​

You are given the root of a binary search tree (BST) and two of its nodes, p and q. Return their lowest common ancestor (LCA): the deepest node that has both p and q somewhere below it. A node counts as being below itself.

A binary search tree is a binary tree with an ordering rule. At every node, every value in its left subtree is smaller than the node's value, and every value in its right subtree is larger.

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

LCA(2, 8) = 6
LCA(2, 4) = 2      (2 is above 4, and 2 counts as being below itself)
LCA(3, 5) = 4

The tree has between 2 and 100,000 nodes. All values are different, p and q are different, and both are in the tree.

What the problem is really asking ​

Picture the paths from the root down to p and to q. They start together at the root, run together for a while, and then split apart. The LCA is the last node they share, the split point.

In an ordinary binary tree, finding that split needs a full search. In a search tree, the ordering tells you which way each target lies, so you never search at all. Stand at a node and compare both targets with it.

  • Both values are smaller than this node. Both targets are in the left subtree, so the split is further down on the left. Go left.
  • Both values are larger. Go right.
  • Anything else. This node is the answer.

"Anything else" covers two situations. Either one target is smaller and the other larger, so they are on opposite sides and their paths split right here. Or one target is this node, and the other is below it. Either way, no deeper node can have both below it, so this is the lowest one that does.

The brute force, and where it wastes work ​

Ignore the ordering, as if this were an ordinary binary tree. Find the path from the root to p, find the path to q, and return the last node the two paths share.

python
def lowestCommonAncestor(root, p, q):
    def path_to(node, target, path):
        if not node:
            return False
        path.append(node)
        if node is target or path_to(node.left, target, path) or path_to(node.right, target, path):
            return True
        path.pop()                          # target not down here, undo
        return False
    a, b = [], []
    path_to(root, p, a)
    path_to(root, q, b)
    i = 0
    while i < min(len(a), len(b)) and a[i] is b[i]:
        i += 1
    return a[i - 1]

This can visit every node, O(n) time, and stores two paths, O(n) memory.

The waste in one sentence: it searches the whole tree for each target, when the ordering already says which direction each target lies at every step.

The solution ​

python
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        node = root                                          # (1)
        while node:                                          # (2)
            if p.val < node.val and q.val < node.val:        # (3)
                node = node.left
            elif p.val > node.val and q.val > node.val:      # (4)
                node = node.right
            else:                                            # (5)
                return node
ts
function lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode {
  let node: TreeNode = root;                                 // (1)
  while (true) {                                             // (2)
    if (p.val < node.val && q.val < node.val) node = node.left!;        // (3)
    else if (p.val > node.val && q.val > node.val) node = node.right!;  // (4)
    else return node;                                        // (5)
  }
}

Line by line ​

(1) Start at the root. Every path starts there, so the root is an ancestor of both targets.

(2) Walk downward. Each step goes one level deeper. The problem promises both targets are in the tree, so the loop always reaches the split point and returns before running out of nodes. If you could not trust that promise, you would check for a missing child.

(3) Both targets are smaller. By the ordering rule, both are in the left subtree. The split point is down there, so go left.

(4) Both targets are larger. Go right.

(5) The split point. The targets are on opposite sides, or one of them is this node. Either way, this is the LCA.

The walk never has to come back up. Each decision is final, because the ordering guarantees which side holds each target. That is why a simple loop with one pointer is enough. A recursive version works too, but it uses O(h) memory for the waiting calls and gains nothing.

Trace ​

Take the tree above.

LCA(2, 8):

StepnodeCompare 2 and 8 with itAction
162 < 6, but 8 > 6opposite sides → return 6

LCA(3, 5):

StepnodeCompare 3 and 5 with itAction
16both smallergo left to 2
22both largergo right to 4
343 < 4, but 5 > 4opposite sides → return 4

LCA(2, 4):

StepnodeCompare 2 and 4 with itAction
16both smallergo left to 2
222 equals the nodeneither "both smaller" nor "both larger" → return 2

Complexity, derived ​

Time. Each step goes down one level, so there are at most h steps, where h is the tree's height. For a balanced tree, h is about \log_2 n. For a tree shaped like a line, h is n. So the time is O(h).

Space. One pointer, so O(1).

Edge cases ​

  • One target is the root. Line (5) fires at the first step.
  • One target is directly above the other. Line (5) fires when the walk reaches the upper one, as in LCA(2, 4).
  • The targets are two leaves far apart. The walk stops where their paths split, which may be the root.
  • A tree shaped like a line. Still correct, but the walk may take n steps.

The ordinary binary tree version ​

LeetCode 236 asks the same question for an ordinary binary tree, with no ordering. Now you really must search.

python
def lowestCommonAncestor(self, root, p, q):
    if not root or root is p or root is q:     # empty, or found a target
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root                            # one target on each side: split here
    return left or right                       # both on one side, or neither

Read what each call returns: "if either target is somewhere in this subtree, return the highest sign of it, otherwise None".

  • If both children return something, one target is on each side, so this node is where the paths split.
  • If only one child returns something, pass it upward. Both targets are on that side, or only one has been found so far.

That is O(n) time and O(h) memory. Knowing both versions, and saying what changed, is the interview answer. The search-tree version is O(h) time and O(1) memory because the ordering does the searching for you.

Variations you will meet ​

  • LCA when each node has a pointer to its parent. Walk up from both nodes to the root and find where the two upward paths meet. That is the same as finding where two linked lists join.
  • Many LCA questions on one fixed tree. Do some work in advance, and each question can then be answered very quickly. That is a more advanced technique, worth naming if asked about scale.

The general lesson: in a search tree, the ordering replaces searching. A problem that needs a full walk of an ordinary tree becomes a single walk down one path.

What the interviewer will push on ​

"Why is the split point the answer?" Below it, the targets are on opposite sides, so no deeper node can have both below it.

"What if one node is above the other?" Line (5) fires when the walk reaches the upper one, and returns it. Correct, because a node counts as being below itself.

"What changes without the search-tree ordering?" You need the recursive search: O(n) instead of O(h).

"What if a target might not be in the tree?" The ordinary-tree version would return a node even if only one target exists. You would need to check both are present.

One thing to volunteer: say that the ordering is doing the searching for you. That framing makes the search-tree version obvious rather than memorised.

Next: 4.14.8 Binary Tree Level Order Traversal. The first breadth-first problem, and the template for four more.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet