Closest Leaf in a Binary Tree
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
You are given the root of a binary tree in which every node has a distinct value, and an integer k that is the value of one of its nodes.
Return the value of the leaf nearest to the node with value k. Distance is the number of edges on the path between two nodes, and a path may go up through parents as well as down. A leaf is a node with no children; the node k itself counts if it is a leaf.
If several leaves are equally near, return the smallest of their values.
Examples
Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 Output: 3
Going down from 2 takes three edges to reach leaf 6, but going up through 1 reaches leaf 3 in two.
Input: root = [1,2,3], k = 3 Output: 3
Node 3 is itself a leaf, at distance 0.
Input: root = [1,2,3], k = 1 Output: 2
Leaves 2 and 3 are both one edge away; 2 is smaller.
Constraints
- The number of nodes is in the range [1, 1000]
- 1 <= Node.val <= 1000
- All values are distinct
- A node with value k exists in the tree
Approaches
- Distance from every leaf by climbing to the meeting point — time O(n · h), space O(n)
Follow-up
What if many targets were asked about the same tree? Run one multi-source BFS from all leaves at once: it gives every node its nearest leaf in O(n), and each query becomes a lookup.
Related problems
Start free on Cariara · Coding problems · System design studio
