Full lesson preview

Find the lowest common ancestor in a binary tree

Given a binary tree and two nodes, find their lowest common ancestor (LCA).

Python practice15 minTrees & Binary TreesIntermediateLast updated March 29, 2026

Problem statement

You are given the root of a binary tree and two nodes p and q (references to nodes inside the tree). Return the lowest common ancestor (LCA) of p and q. The LCA of two nodes p and q is the lowest node in the tree that has both p and q as descendants (we allow a node to be a descendant of itself). You may assume both p and q exist in the tree and each node has a unique value. Implement the function lowest_common_ancestor(root, p, q) which returns the TreeNode that is the LCA.

Task

Implement a function lowest_common_ancestor(root, p, q) that returns the LCA node for two given nodes p and q in a binary tree.

Examples

Example - nodes in different subtrees

Input

root = TreeNode(3, TreeNode(5), TreeNode(1)), p = root.left (value 5), q = root.right (value 1)

Output

The root (3) is the lowest node that has both 5 and 1 as descendants.

Input format

A binary tree root and two TreeNode references p and q (both are nodes inside the tree).

Output format

Return the TreeNode that is the lowest common ancestor of p and q. Tests compare the node's value via its string representation.

Constraints

The number of nodes is in the range [1, 10^4]. Node values are unique. p and q are guaranteed to exist in the tree.

Samples

Sample 1

Input

root = TreeNode(3, TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), TreeNode(4))), TreeNode(1, TreeNode(0), TreeNode(8))); p = node 5; q = node 1

Output

Nodes 5 and 1 are in different subtrees; the LCA is the root 3.