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. If there are multiple cases, you should follow these priorities:

1. The leaf node is in the left subtree of the node with k;

2. The leaf node is in the right subtree of the node with k;

3. The leaf node is not in the subtree of the node with k.

4. root represents a binary tree with at least 1 node and at most 1000 nodes.

5. Every node has a unique node.val in range [1, 1000][1,1000].

6. There exists a node in the given binary tree for which node.val == k.

Clarification

A node is called a leaf if it has no children.

About binary tree representation

Example

Example 1:

Input: {1, 3, 2}, k = 1
Output: 3
Explanation:
    1
   / \
  3   2

Example 2:

Input: {1}, k = 1
Output: 1

// Graph solution
public class Solution {
    // Graph of Integer(Node) -> List of Neighbors(with leaf status)
    Map<Integer, ArrayList<int[]>> graph;
    boolean targetIsLeaf = false;

    // Every node has a unique value
    public int findClosestLeaf(TreeNode root, int k) {
        // Creating undirected graph
        graph = new HashMap<>();
        DFS(root, k);
        if (targetIsLeaf)
            return k;
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        visited.add(k);
        q.add(k);
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                int node = q.poll();
                for (int i = graph.get(node).size() - 1; i >= 0; i--) {
                    int[] x = graph.get(node).get(i);
                    if (!visited.contains(x[0])) {
                        visited.add(x[0]);
                        if (x[1] == 1)
                            return x[0];
                        q.add(x[0]);
                    }
                }
            }
        }
        return -1;
    }

    public void DFS(TreeNode root, int target) {
        graph.computeIfAbsent(root.val, k -> new ArrayList<>());
        if (root.left == null && root.right == null) {
            if (target == root.val)
                targetIsLeaf = true;
            return;
        }
        if (root.right != null) {
            graph.get(root.val)
                    .add(new int[] { root.right.val, (root.right.left == null && root.right.right == null) ? 1 : 0 });
            graph.computeIfAbsent(root.right.val, k -> new ArrayList<>()).add(new int[] { root.val, 0 });
            DFS(root.right, target);
        }
        if (root.left != null) {
            graph.get(root.val)
                    .add(new int[] { root.left.val, (root.left.left == null && root.left.right == null) ? 1 : 0 });
            graph.computeIfAbsent(root.left.val, k -> new ArrayList<>()).add(new int[] { root.val, 0 });
            DFS(root.left, target);
        }
    }
}

// Tree Solution
public class Solution {
    static class Pair {
        int node, dist;

        Pair(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

    Pair[][] distances;
    int closestLeaf = 0;

    public int findClosestLeaf(TreeNode root, int k) {
        distances = new Pair[1001][];
        fillDistances(root);
        findAnswer(root, k, new Pair(-1, Integer.MAX_VALUE));
        return closestLeaf;
    }

    public Pair fillDistances(TreeNode root) {
        if (root.left == null && root.right == null) {
            distances[root.val] = new Pair[] { new Pair(root.val, 0), new Pair(root.val, 0) };
            return new Pair(root.val, 0);
        }
        Pair leftLeaf = new Pair(-1, Integer.MAX_VALUE);
        if (root.left != null) {
            leftLeaf = fillDistances(root.left);
            leftLeaf.dist++;
        }
        Pair rightLeaf = new Pair(-1, Integer.MAX_VALUE);
        if (root.right != null) {
            rightLeaf = fillDistances(root.right);
            rightLeaf.dist++;
        }
        distances[root.val] = new Pair[] { leftLeaf, rightLeaf };
        return leftLeaf.dist <= rightLeaf.dist ? new Pair(leftLeaf.node, leftLeaf.dist)
                : new Pair(rightLeaf.node, rightLeaf.dist);
    }

    public boolean findAnswer(TreeNode root, int k, Pair closestLeafFromParent) {
        if (root.val == k) {
            if (distances[root.val][0].dist <= distances[root.val][1].dist
                    && distances[root.val][0].dist <= closestLeafFromParent.dist)
                closestLeaf = distances[root.val][0].node;
            else if (distances[root.val][1].dist < distances[root.val][0].dist
                    && distances[root.val][1].dist <= closestLeafFromParent.dist)
                closestLeaf = distances[root.val][1].node;
            else
                closestLeaf = closestLeafFromParent.node;
            return true;
        }
        if (root.left == null && root.right == null)
            return false;
        if (root.left != null) {
            boolean ans = findAnswer(root.left, k,
                    distances[root.val][1].dist == Integer.MAX_VALUE ? distances[root.val][1]
                            : new Pair(distances[root.val][1].node, distances[root.val][1].dist + 1));
            if (ans)
                return true;
        }
        if (root.right != null) {
            boolean ans = findAnswer(root.right, k,
                    distances[root.val][0].dist == Integer.MAX_VALUE ? distances[root.val][0]
                            : new Pair(distances[root.val][0].node, distances[root.val][0].dist + 1));
            if (ans)
                return true;
        }
        return false;
    }
}