742. Closest Leaf in a Binary Tree


Given a binary tree where every node has a unique value, and a target key k, find the value of the nearest leaf node to target k in the tree.

Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1: 

Input:
root = [1, 3, 2], k = 1
Diagram of binary tree:
          1
         / \
        3   2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.

Example 2: 

Input:
root = [1], k = 1
Output: 1

Explanation: The nearest leaf node is the root node itself.

Example 3: 

Input:
root = [1,2,3,4,null,null,null,5,null,6], k = 2
Diagram of binary tree:
             1
            / \
           2   3
          /
         4
        /
       5
      /
     6

Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

Note:

  1. root represents a binary tree with at least 1 node and at most 1000 nodes.
  2. Every node has a unique node.val in range [1, 1000].
  3. There exists some node in the given binary tree for which node.val == k.


b'
\n
\n\n
\n

Approach #1: Convert to Graph [Accepted]

\n

Intuition

\n

Instead of a binary tree, if we converted the tree to a general graph, we could find the shortest path to a leaf using breadth-first search.

\n

Algorithm

\n

We use a depth-first search to record in our graph each edge travelled from parent to node.

\n

After, we use a breadth-first search on nodes that started with a value of k, so that we are visiting nodes in order of their distance to k. When the node is a leaf (it has one outgoing edge, where the root has a "ghost" edge to null), it must be the answer.

\n\n

Complexity Analysis

\n
    \n
  • \n

    Time Complexity: where is the number of nodes in the given input tree. We visit every node a constant number of times.

    \n
    • \n
  • \n

    Space Complexity: , the size of the graph.

    \n
    • \n
\n
\n

Approach #2: Annotate Closest Leaf [Accepted]

\n

Intuition and Algorithm

\n

Say from each node, we already knew where the closest leaf in it\'s subtree is. Using any kind of traversal plus memoization, we can remember this information.

\n

Then the closest leaf to the target (in general, not just subtree) has to have a lowest common ancestor with the target that is on the path from the root to the target. We can find the path from root to target via any kind of traversal, and look at our annotation for each node on this path to determine all leaf candidates, choosing the best one.

\n\n

Complexity Analysis

\n
    \n
  • Time and Space Complexity: . The analysis is the same as in Approach #1.
    • \n
\n
\n

Analysis written by: @awice.

\n
'