Sign in
Skip to solution
mediumDSA

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

1.1k views
01

Understand the problem

Explain LCA.

treeslca
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Recurse: if the current node is null or one of the targets, return it. Recurse left and right; if both sides return non-null, the current node is the LCA; otherwise propagate the non-null side up. O(n).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

LCA in a general binary tree
Run Playground
class TreeNode:
    def __init__(self, val, 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:
        return root            # targets split here -> LCA
    return left or right       # propagate the non-null side


# --- demo ---  tree: 3 / (5 / 4,7) , 1
n4, n7 = TreeNode(4), TreeNode(7)
root = TreeNode(3, TreeNode(5, n4, n7), TreeNode(1))
print(lowest_common_ancestor(root, n4, n7).val)   # 5
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 29 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track