Lowest Common Ancestor

Finding the Lowest Common Ancestor in a binary tree is a classic problem that tests your understanding of tree traversals and recursion. It's important because it demonstrates your ability to efficiently navigate complex data structures.

treebinary treerecursionlowest common ancestordepth-first search

Problem Statement

Given a binary tree and two specific nodes within that tree, identify the lowest common ancestor (LCA) of those two nodes. The LCA is defined as the deepest node in the tree that has both input nodes as descendants (where we allow a node to be a descendant of itself). You are guaranteed that both nodes exist in the tree and that all node values are unique.

Example 1

Input: tree: {6: {2: {0: null, 4: {3: null, 5: null}}, 8: {7: null, 9: null}}}, node1: 2, node2: 8

Output: 6

The lowest common ancestor of nodes 2 and 8 is the root node, 6, because it's the deepest node that has both 2 and 8 as descendants.

Example 2

Input: tree: {6: {2: {0: null, 4: {3: null, 5: null}}, 8: {7: null, 9: null}}}, node1: 3, node2: 5

Output: 4

The lowest common ancestor of nodes 3 and 5 is node 4, as it's the deepest node that has both 3 and 5 as descendants.

Constraints

-The tree contains only unique values.
-Both target nodes (node1 and node2) are guaranteed to exist in the tree.
-The number of nodes in the tree is between 1 and 1000.
-Node values are integers between 0 and 1000.
-The tree is a valid binary tree.

Brute Force Approach

A brute-force approach would involve traversing the tree to find the paths from the root to each of the two target nodes. Then, you'd compare these paths to find the common ancestor that is furthest from the root. This is like exploring a maze by trying every possible path from the entrance until you find the two exits you're looking for, and then tracing back to find the last intersection they shared. This approach is inefficient because it involves redundant traversals of the tree.

TimeO(n^2)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem