Binary Tree Step by Step Directions from One Node to Another

Question

I am trying to solve LeetCode question 2096. Step-By-Step Directions From a Binary Tree Node to Another:

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

• 'L' means to go from a node to its left child node.
• 'R' means to go from a node to its right child node.
• 'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

I have converted the tree to a graph using an adjacency list. For each node, I store the adjacent nodes as well as the direction. For example, suppose we have a tree [1,2,3], then at the end of traversal, we obtain a HashMap that looks like {1:[(2,'L'), (3,'R')], 2:[(1,'U')], 3:[(1,'U')].

I assumed that performing a BFS from startNode to endNode would help me trace the path. But I end up getting an incorrect answer or an extra step if the endNode was in the left but I tried the right node first or if I tried the right node first and the endNode was left.

I found on Stack Overflow How to trace the path in a Breadth-First Search? and it seems that my approach appears to be correct (I don't know what I am missing). I don't understand the purpose or the need to backtrace either.

My code is below:

public class StepByStep {

    HashMap<TreeNode, HashMap<TreeNode, String>> graph = new HashMap<TreeNode, HashMap<TreeNode, String>>();

    public static void main(String argv[]) {
        TreeNode root = new TreeNode (5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(4);
        StepByStep sbs = new StepByStep();
        System.out.println(sbs.getDirections(root, 3, 6));
        Set<TreeNode> keys = sbs.graph.keySet();
        for(TreeNode key : keys) {
            System.out.print(key.val + " ");
            HashMap<TreeNode, String> map = sbs.graph.get(key);
            Set<TreeNode> nodes = map.keySet();
            for(TreeNode node : nodes) {
                System.out.print(node.val + map.get(node) + " ");
            }
            System.out.println();
        }
    }

    public String getDirections(TreeNode root, int startValue, int destValue) {
        // we do a inorder traversal
        inorder(root, null);
        //now we perform a breadth first search using the graph
        Set<TreeNode> keys = graph.keySet();
        TreeNode start = null;
        for(TreeNode key : keys) {
            if(key.val == startValue) {
                start = key;
                break;
            }
        }
        return bfs(start, destValue);
    }
    
    public String bfs(TreeNode root, int destValue) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        queue.add(root);
        StringBuilder sb = new StringBuilder("");
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {
                TreeNode current = queue.poll();
                if(current.val == destValue) {
                    return sb.toString();
                }
                visited.add(current);
                HashMap<TreeNode, String> map = graph.get(current);
                Set<TreeNode> keys = map.keySet();
                for(TreeNode key : keys) {
                    if(!visited.contains(key)) {
                        sb.append(map.get(key));
                        queue.add(key);
                    }
                }
                --size;
            }
        }
        return "";
    }

    public void inorder(TreeNode root, TreeNode parent) {
        if (root == null)
            return;
        inorder(root.left, root);
        inorder(root.right, root);
        if (root.left != null) {
            if (!graph.containsKey(root)) {
                graph.put(root, new HashMap<TreeNode, String>());
            }
            HashMap<TreeNode, String> map = graph.get(root);
            map.put(root.left, "L");
            graph.put(root, map);
        }
        if (root.right != null) {
            if (!graph.containsKey(root)) {
                graph.put(root, new HashMap<TreeNode, String>());
            }
            HashMap<TreeNode, String> map = graph.get(root);
            map.put(root.right, "R");
            graph.put(root, map);
        }
        if (parent != null) {
            if (!graph.containsKey(root)) {
                graph.put(root, new HashMap<TreeNode, String>());
            }
            HashMap<TreeNode, String> map = graph.get(root);
            map.put(parent, "U");
            graph.put(root, map);
        }
    }
}

What am I missing?

Answer 1

The problem is in bfs: there you add every visited node to sb, but that is wrong, since these nodes are not all on the path from the root to that particular node. Instead, you should consider that every visited node represents its own unique path from the root, which does not include all the nodes that were already visited, just a few of those.

One solution is that you store in the queue not only the node, but also its own move-string (like its private sb), so that you actually store a Pair in the queue: a node and a string buffer.

Once you find the destination, you can then return that particular string.

Alternatively, you'd make life easier if you would perform a depth-first search (with recursion), building the string while backtracking. This will cost less memory. Breadth first is interesting when you need to find a shortest path, but in a tree there is only one path between two nodes, so finding any path is good enough, and that is what a depth-first search will give you.

Finally, I would solve this problem as follows:

• Perform a depth first traversal, and collect the steps ("L" or "R") from the root to the start node and the steps from the root to the destination node. These paths only have the letters "L" and "R" as there is no upwards movement.

• Remove the common prefix from these paths, so that both paths now start from their lowest common ancestor node.

• Replace all letters of the first path (if any) with "U".

• Done.