Print root to node path in BT

Intuition

To determine the path from the root to a specific node in a binary tree, a Depth-First Search (DFS) strategy is employed. This technique involves initializing a vector to record the current path and then performing a recursive traversal of the tree. At each node, the algorithm checks if it is null, which would signify the end of a path and prompt a return of false. If the node’s value matches the target value, the traversal is complete, and true is returned, indicating that the target node has been successfully located.

During the traversal, the value of each visited node is added to the path vector. The algorithm proceeds by recursively exploring both the left and right subtrees. If the target node is not found in the current path, the algorithm backtracks by removing the last node from the path vector, allowing exploration of alternative paths. Ultimately, the function returns a vector that represents the path from the root to the specified target node.

Approach

Begin by initializing an empty vector to hold the current path from the root to the target node.
Define a recursive function to perform a Depth-First Search (DFS). Start the traversal from the root node and explore the tree following an in-order sequence.
In the recursive function, return false if the current node is null, indicating that the end of the current path has been reached. Return true if the current node’s data matches the target value, signaling that the path has been successfully found.
During each recursive call, append the current node's value to the path vector. Check if the node’s value equals the target value. Recursively call the function for both the left and right children of the current node.
If the target node is not found along the current path, remove the last node from the vector to backtrack and explore other potential paths.
Finally, return the vector that contains the path from the root node to the target node once the target is found.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> allRootToLeaf(TreeNode* root) {
        vector<vector<int>> allPaths; // Vector to store all root-to-leaf paths
        vector<int> currentPath; // Vector to store the current path
        
        dfs(root, currentPath, allPaths);
        
        return allPaths;
    }

private:
    void dfs(TreeNode* node, vector<int>& path, vector<vector<int>>& allPaths) {
        if (!node) {
            return; // Base case: return if the current node is null
        }
        // Add the current node's data to the path
        path.push_back(node->data);

        if (!node->left && !node->right) {
            // Add the path to allPaths if it's a leaf node
            allPaths.push_back(path); 
        } else {
            // Recursively call the function on the left child
            dfs(node->left, path, allPaths); 
            // Recursively call the function on the right child
            dfs(node->right, path, allPaths); 
        }
         // Backtrack by removing the last node from the path 
        path.pop_back();
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    Solution solution;
    vector<vector<int>> paths = solution.allRootToLeaf(root);

    for (const auto& path : paths) {
        for (int val : path) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}
import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { 
        data = val; 
        left = null; 
        right = null; 
    }
}

class Solution {
    public List<List<Integer>> allRootToLeaf(TreeNode root) {
        // List to store all root-to-leaf paths
        List<List<Integer>> allPaths = new ArrayList<>();
        // List to store the current path
        List<Integer> currentPath = new ArrayList<>();
        
        // Helper function to perform DFS
        dfs(root, currentPath, allPaths);
        
        return allPaths;
    }

    private void dfs(TreeNode node, List<Integer> path, List<List<Integer>> allPaths) {
        if (node == null) {
            return; // Base case: return if the current node is null
        }

        path.add(node.data); // Add the current node's data to the path

        if (node.left == null && node.right == null) {
        // Add the path to allPaths if it's a leaf node
            allPaths.add(new ArrayList<>(path)); 
        } else {
            // Recursively call the function on the left child
            dfs(node.left, path, allPaths); 
            // Recursively call the function on the right child
            dfs(node.right, path, allPaths); 
        }
        // Backtrack by removing the last node from the path
        path.remove(path.size() - 1); 
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.allRootToLeaf(root));
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def allRootToLeaf(self, root):
        # Initialize an empty list to store all paths
        all_paths = []
        
        # Helper function to perform DFS and find all paths
        def dfs(node, path):
            if not node:
                return
            
            # Append the current node's data to the path
            path.append(node.data)
            
            # If it's a leaf node, append the path to all_paths
            if not node.left and not node.right:
                all_paths.append(list(path))
            else:
                # Recursively call the function on the left and right children
                dfs(node.left, path)
                dfs(node.right, path)
            
            # Backtrack by removing the current node from the path
            path.pop()
        
        # Call the helper function with the root node and an empty path
        dfs(root, [])
        
        return all_paths

# Example usage:
if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    
    solution = Solution()
    print(solution.allRootToLeaf(root))
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.data = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 **/

class Solution {
    allRootToLeaf(root) {
        // List to store all root-to-leaf paths
        const allPaths = [];
        // List to store the current path
        const currentPath = [];
        
        // Helper function to perform DFS
        const dfs = (node, path) => {
            if (node === null) {
                return; // Base case: return if the current node is null
            }
            // Add the current node's data to the path
            path.push(node.data); 

            if (node.left === null && node.right === null) {
                // Add the path to allPaths if it's a leaf node
                allPaths.push([...path]); 
            } else {
                // Recursively call the function on the left child
                dfs(node.left, path); 
                // Recursively call the function on the right child
                dfs(node.right, path); 
            }

            // Backtrack by removing the last node from the path
            path.pop(); 
        };
        
        // Start the DFS from the root node
        dfs(root, currentPath);
        
        return allPaths;
    }
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const solution = new Solution();
console.log(solution.allRootToLeaf(root));

Complexity Analysis

Time Complexity : O(N) where N is the number of nodes in the binary tree. Each node of the binary tree is visited exactly once during the traversal.

Space Complexity : O(N) where N is the number of nodes in the binary tree. This is because the stack can potentially hold all nodes in the tree when dealing with a skewed tree (all nodes have only one child), consuming space proportional to the number of nodes.

Problem List

Print root to node path in BT

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code