Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Medium

Lowest Common Ancestor of a Binary Tree

Lowest common ancestor of a binary tree explained: the post-order recursion where both sides report back, tested Python code, edge cases and a live tree visual.

Also searched as: LCA of two nodes in a binary tree · lowest common ancestor recursive solution

🌳

Try it live Free

Binary Search Tree & Traversals

Build a tree in the BST lab and pick two values on different sides of a node: trace how that node is the first one whose left and right subtrees each contain one of them.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given a binary tree (not necessarily a BST) and two distinct nodes p and q in it, return their lowest common ancestor: the deepest node with both in its subtree, where a node may be its own ancestor.

Inputroot = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output3
Inputsame tree, p = 5, q = 4
Output5

5 is an ancestor of 4.

The key insight

Ask every subtree one question: "do you contain p or q?" and have it return the node it found (or None). If a node gets a non-null answer from both its left and right sides, p and q are on different sides, so this node is the LCA. If only one side answers, pass that answer upward. A node equal to p or q returns itself immediately.

Brute force first: Record the root-to-p and root-to-q paths, then walk both until they diverge: also O(n) but needs two searches and extra lists.

Step-by-step approach

  1. If the node is None, or is p or q, return the node.
  2. Recurse into the left subtree and the right subtree.
  3. If both calls return a node, the current node is the LCA: return it.
  4. Otherwise return whichever call returned a node (or None).

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:                 # p and q are on different sides
        return root
    return left or right

Complexity

TimeO(n)
SpaceO(h)

In the worst case every node is visited once. The recursion depth is the height h of the tree.

Common mistakes

Frequently asked questions

What is the time and space complexity of LCA in a binary tree?

O(n) time since each node may be visited once, and O(h) space for the recursion stack, where h is the height.

Why can we return p as soon as we find it?

If q lies under p, then p is the LCA and nothing below changes that. If q is elsewhere, an ancestor will receive p from one side and q from the other and return itself.

What if nodes have parent pointers?

Then it becomes the intersection of two linked lists: walk up from p and q, or record p's ancestors in a set and walk up from q until you hit one.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.