Root to Leaf Paths

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Print all root-to-leaf paths in a binary tree. DFS tracking current path.

Algorithm

1DFS. Append current node to path. At leaf: print/store path. Backtrack by removing last node.

Common Pitfalls

•Use list to track path. Backtrack: remove last element after both recursive calls return.

Root to Leaf Paths.java

Java

// Approach: DFS with backtracking. Maintain current path and print on reaching a leaf.
// Time: O(n) Space: O(h)
import java.util.*;

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    public static ArrayList<ArrayList<Integer>> Paths(Node root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;

        ArrayList<Integer> currentPath = new ArrayList<>();
        findPaths(root, currentPath, result);
        return result;
    }

    private static void findPaths(Node node, ArrayList<Integer> currentPath, ArrayList<ArrayList<Integer>> result) {
        if (node == null)
            return;

        currentPath.add(node.data);

        if (node.left == null && node.right == null)
            result.add(new ArrayList<>(currentPath));
        else {
            findPaths(node.left, currentPath, result);
            findPaths(node.right, currentPath, result);
        }

        currentPath.remove(currentPath.size() - 1);
    }
}

Was this solution helpful?