How do you find the lowest common ancestor in a binary tree?

Q: How do you find the lowest common ancestor in a binary tree?

**Target Audience:** Beginners preparing for coding interviews — you should know what a binary tree and a recursive function are; everything else is explained. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Two cousins at a family reunion are arguing about how they are related. Someone pulls out the family tree. You put a finger on each cousin and move both fingers upward, generation by generation, until they land on the same person. That person — the first shared one, the youngest relative they both descend from — is their **lowest common ancestor**. T

The problem

Question presented to candidate: "Given the root of a binary tree — not necessarily a binary search tree — and two nodes p and q that are in the tree, write a Python function that returns their lowest common ancestor: the deepest node that has both p and q as descendants, where a node counts as a descendant of itself."

What a strong answer should cover:

The definition, including that p can be the answer when it is an ancestor of q.
The recursive post-order search: return the node if it is null, p or q; if both children return non-null, the current node is the LCA.
O(n) time and O(h) space, and why the early return is safe only when both nodes exist.
How to handle a possibly missing node (count matches, no early return) and the parent-map alternative.
Python details: compare nodes with is (identity), nodes hash by identity so they work as dict keys, and the 1000-frame recursion limit on deep trees.
The BST shortcut and why it does not apply to a general binary tree.

Clarifying questions expected:

Is it a BST or a general binary tree?
Are both nodes guaranteed to be in the tree, and are they given as nodes or as values?

Code / implementation expected: Yes — lca(root, p, q) returning a node, in Python 3.

trees
lca

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what a binary tree and a recursive function are; everything else is explained.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Two cousins at a family reunion are arguing about how they are related. Someone pulls out the family tree. You put a finger on each cousin and move both fingers upward, generation by generation, until they land on the same person. That person — the fir

The solution is hidden so you can try first

13 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonRecursive LCA: six queries on one tree

Practice

PythonParent map cross-check and the missing-node trap

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.