/**
* 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:
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);
}
}