Nearest Leaf From a Node

Medium

You are given the root of a binary tree whose values are all distinct, and an integer start, the value of one of its nodes. A leaf is a node with no children. The distance between two nodes is the number of edges on the path between them, and a path may go down to children as well as up to parents. Find the leaf closest to the node with value start and return its value. If start is a leaf itself, the answer is start. The tests are built so that the closest leaf is unique.

Example 1

root=tree_node([10, 20, 30, None, None, 40, 50, 60]), start=40 → 60

Below node 40 is the leaf 60, one edge away. Leaf 50 takes two edges through the parent 30, and leaf 20 is even farther.

Example 2

root=tree_node([3, 8, None, 6, None, 1]), start=8 → 1

The root 3 has a child, so it is not a leaf. The only leaf is 1, two edges down.

Example 3

root=tree_node([5]), start=5 → 5

A single-node tree: the node itself is a leaf at distance 0.

Constraints

1 ≤ number of nodes ≤ 1000
1 ≤ Node.val ≤ 1000
All values are distinct
A node with value start exists
The closest leaf to it is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Similar problems

The Tree Seen From the Right Medium Tree Columns, Top Down Medium First Value on the Lowest Row Medium Largest Value on Each Tree Level Medium Insert a Tree Level Medium

Input

root=tree_node([10, 20, 30, None, None, 40, 50, 60]), start=40

Expected

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