LeetCode 2096: Step-By-Step Directions From a Binary Tree Node to Another Solution

Master LeetCode problem 2096 (Step-By-Step Directions From a Binary Tree Node to Another), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2096. Step-By-Step Directions From a Binary Tree Node to Another

Medium

String Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a depth-first search (DFS) from the start node to the destination node while keeping track of the path taken. At each step, we can explore the left child, right child, and parent of the current node. We will continue until we reach the destination node and then construct the step-by-step directions based on the path taken.

Perform a DFS from the start node to the destination node, keeping track of the path taken.
At each step, explore the left child, right child, and parent of the current node.
When the destination node is reached, construct the step-by-step directions based on the path taken.

Time complexity: O(n) where n is the number of nodes in the binary tree. Space complexity: O(n) for the recursive call stack.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public String findPath(TreeNode root, int startValue, int destValue) {
        TreeNode startNode = findNode(root, startValue);
        TreeNode destNode = findNode(root, destValue);
        List<TreeNode> path = new ArrayList<>();
        dfs(root, startNode, destNode, path);

        StringBuilder directions = new StringBuilder();
        for (int i = 1; i < path.size(); i++) {
            TreeNode prev = path.get(i - 1);
            TreeNode curr = path.get(i);
            if (prev.left == curr) {
                directions.append("L");
            } else if (prev.right == curr) {
                directions.append("R");
            } else {
                directions.append("U");
            }
        }
        return directions.toString();
    }

    private TreeNode findNode(TreeNode node, int value) {
        if (node == null) return null;
        if (node.val == value) return node;

        TreeNode left = findNode(node.left, value);
        TreeNode right = findNode(node.right, value);

        return left != null ? left : right;
    }

    private boolean dfs(TreeNode node, TreeNode start, TreeNode dest, List<TreeNode> path) {
        if (node == null) return false;

        path.add(node);
        if (node == dest) return true;

        if (dfs(node.left, start, dest, path) || dfs(node.right, start, dest, path)) {
            return true;
        }

        path.remove(path.size() - 1);
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2096 (Step-By-Step Directions From a Binary Tree Node to Another)?

This page provides optimized solutions for LeetCode problem 2096 (Step-By-Step Directions From a Binary Tree Node to Another) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2096 (Step-By-Step Directions From a Binary Tree Node to Another)?

The time complexity for LeetCode 2096 (Step-By-Step Directions From a Binary Tree Node to Another) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2096 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2096 in Java, C++, or Python.

Back to LeetCode Solutions