742. Closest Leaf in a Binary Tree

/**

 * 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.\

*/

The problem is unique in that it poses a problem where the tree needs to be transformed into a graph.

See my solution to the problem here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trees/ClosestLeafInABinaryTree.java

The question is interesting where you are given a tree and asked to find the closest leaf to a given node. Interestingly the leaf could occur in one of the children of a node or instead in the parent of a node.

With a tree we can only traverse down and can’t traverse up into the parent nodes. So the approach here is to transform the tree into a graph while recording the node requested for search and then traversing the graph via bfs to find the closest leaf node.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public int findClosestLeaf(TreeNode root, int k) {
    //handle root separately
    if (root.val == k && root.left == null && root.right == null) return k;
    recurseTree(root, k, null);
    return bfs(searchNode, root.val);
}
 
/**
 * do a BFS of the tree starting from the target node. as soon as you find the first leaf node stop.
 *
 * @param startNode
 * @param rootVal
 * @return
 */
int bfs(Node startNode, int rootVal) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(startNode);
    Set<Node> visited = new HashSet<>();
    while (!queue.isEmpty()) {
        int iQueueSize = queue.size();
        for (int i = 0; i < iQueueSize; i++) {
            Node node = queue.poll();
            //don't process root as a leaf node as root can have a single child and thus be treated as a leaf node
            //checking for size as 1 since node has link to parent
            if (node.children.size() == 1 && node.val != rootVal) {
                return node.val;
            }
            visited.add(node);
            for (Node child : node.children) {
                if (!visited.contains(child)) {
                    queue.add(child);
                }
            }
        }
    }
    return 0;
}
 
/**
 * traverse the tree and transform it into a graph
 *
 * @param treeNode
 * @param k
 * @param parent
 */
void recurseTree(TreeNode treeNode, int k, Node parent) {
    Node theNode = new Node(treeNode.val);
    if (treeNode.val == k) {
        searchNode = theNode;
    }
    if (parent != null) {
        parent.children.add(theNode);
        theNode.children.add(parent);
    }
    if (treeNode.left != null) {
        recurseTree(treeNode.left, k, theNode);
    }
    if (treeNode.right != null) {
        recurseTree(treeNode.right, k, theNode);
    }
}