# [Question] Find Cloest Leaf in Binary Tree

### Question

Given a Binary Tree and a key, find distance of the closest leaf.

Examples:

``````          1
/    \
2       3
/   \
5     6
/       \
7         8
/ \       /
9  10     11

Closest key to '8' is '11', so distance is 1 for '8'
Closest key to '3' is '2', so distance is 2 for '3'
Closest key to '5' is either '9' or '10', so distance is 2 for '5'
Closest key to '2' is '2' itself, so distance is 0 for '2'
``````

### Solution

traverse the given tree in preorder and keep track of ancestors (in a caching data struture, either it’s List or an array with a correct pointer)

When we find our target, we do 2 things:

1. find closest distance on lower subtrees of current node.

2. for every ancester, find the closest distance on lower subtrees, then add with distance to ancester.

Finally, return the smallest value seen above.

### Code

Inspired by the code from G4G

``````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));
}
}
``````