## Wednesday, May 16, 2018

### LeetCode 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 closest leaf node to target `k` in the tree.
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.

```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 closest 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`.

``````int answer;

public int findClosest(TreeNode root, int key) {
helper(root, key, new ArrayList<TreeNode>());
}

private void helper(TreeNode node, int key, List<TreeNode> path) {
if (node == null) {
return;
} else if (node.val != key) {
helper(node.left, key, path);
helper(node.right, key, path);
path.remove(path.size() - 1);
} else {
// key matches with current node value
// answer initially = cloest leaf from lower

int len = path.size();
for (int i = 0; i < len; i++) {
// for every ancestor, calculate distance and compare
int ithToLowerLeaf = lenToLowerLeaf(path.get(i));
}
}
}

private int lenToLowerLeaf(TreeNode node) {
if (node == null) {
return Integer.MAX_VALUE;
} else if (node.left == null && node.right == null) {
return 0;
} else {
return 1 + Math.min(lenToLowerLeaf(node.left), lenToLowerLeaf(node.right));
}
}``````