Where the Deepest Leaves Meet

Medium

You are given the root of a binary tree. The root has depth 0, and every child is one level deeper than its parent. A leaf is a node with no children. Take the deepest leaves of the tree and find the lowest node where their paths up to the root come together. In other words, find the deepest node whose subtree contains all of the deepest leaves (a node counts as part of its own subtree). Return that node; the whole subtree hanging from it is checked.

Example 1

root=tree_node([10, 4, 7, 1, None, 3, 8, 6, None, None, None, 2]) → [10, 4, 7, 1, None, 3, 8, 6, None, None, None, 2]

The deepest leaves are 6 (under 1) and 2 (under 8), both at depth 3. The lowest node above both of them is the root 10, so the answer is the whole tree.

Example 2

root=tree_node([5, 9, 2, None, None, 11, 14]) → [2, 11, 14]

The deepest leaves are 11 and 14, and their common ancestor is node 2. Return the subtree rooted at 2.

Example 3

root=tree_node([3, 0, None, None, 12]) → [12]

There is only one deepest leaf, 12, and a single node is its own answer.

Constraints

1 ≤ number of nodes ≤ 1000
0 ≤ Node.val ≤ 1000
All node values are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Hash Table Binary Tree

Similar problems

Tree Columns, Top Down Medium Smallest Cover of the Bottom Row Medium Hops Between Two Keys Medium Spread Through the Tree Medium Replace With Cousin Sums Medium

Input

root=tree_node([10, 4, 7, 1, None, 3, 8, 6, None, None, None, 2])

Expected

[10, 4, 7, 1, None, 3, 8, 6, None, None, None, 2]

Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.