DEV Community

Dev Cookies
Dev Cookies

Posted on

🌳 Blog 5: Path-Based Problems in Binary Trees

🔍 Why This Pattern Matters?

Many tree problems boil down to finding paths:

  • Root → leaf path
  • Any node → any node path
  • Path sum conditions
  • Collecting path values (like printing all root-to-leaf numbers)

If you identify a problem asking for path-based properties, the solution almost always involves DFS (depth-first traversal) with a backtracking approach.

🛠 Core Idea (Template)

For any node:

  1. Add current node to path.
  2. If leaf → process path (check sum, print, collect).
  3. DFS left and right.
  4. Backtrack (remove last node). 
class Solution {
    List<List<Integer>> allPaths = new ArrayList<>();

    public List<List<Integer>> binaryTreePaths(TreeNode root) {
        dfs(root, new ArrayList<>());
        return allPaths;
    }

    private void dfs(TreeNode node, List<Integer> path) {
        if (node == null) return;

        path.add(node.val);

        if (node.left == null && node.right == null) {
            allPaths.add(new ArrayList<>(path));  // leaf reached
        } else {
            dfs(node.left, path);
            dfs(node.right, path);
        }

        path.remove(path.size() - 1); // backtrack
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Classic Problems

1. All Root-to-Leaf Paths (LeetCode 257)

  • Collect all paths in a list.
  • Template above solves it directly.

2. Path Sum (I & II) (LeetCode 112, 113)

  • Check if there exists a root-to-leaf path with given sum.
  • Collect all such paths if multiple exist. 
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == targetSum;
        return hasPathSum(root.left, targetSum - root.val) 
            || hasPathSum(root.right, targetSum - root.val);
    }
}
Enter fullscreen mode Exit fullscreen mode

For Path Sum II, extend with path list like template above.

3. Maximum Path Sum (Any Node → Any Node) (LeetCode 124)

  • Trickier: Path doesn’t have to start at root or end at leaf.
  • Need global max + recursion that returns “max gain” from one side. 
class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        maxSum = Math.max(maxSum, node.val + left + right);

        return node.val + Math.max(left, right);
    }
}
Enter fullscreen mode Exit fullscreen mode

4. Print Numbers Formed by Root-to-Leaf Paths (LeetCode 129)

  • Example: Tree root-to-leaf path 1 → 2 → 3 forms number 123.
  • Sum of all root-to-leaf numbers is required. 
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int num) {
        if (node == null) return 0;

        num = num * 10 + node.val;

        if (node.left == null && node.right == null) return num;

        return dfs(node.left, num) + dfs(node.right, num);
    }
}
Enter fullscreen mode Exit fullscreen mode

🚀 Advanced Variations

  1. Longest Path with Given Condition
  • E.g., Longest path with equal values, or constrained by sum.
  1. Count Paths with Given Sum (Prefix Sum Trick) (LeetCode 437)
  • Instead of root-to-leaf, path can start and end anywhere.
  • Use prefix sum + HashMap to count valid paths efficiently.
  1. Print Path Between Two Nodes
  • Use LCA + root-to-node path and merge.

🎯 Quick Pattern Checklist

  • ✅ If problem asks for root-to-leaf paths → DFS + backtracking.
  • ✅ If problem asks for path sum check → DFS with sum carried forward.
  • ✅ If problem asks for max/min path sum → DFS returning best child + global update.
  • ✅ If path is between any nodes → LCA + path decomposition.

🔥 Key Takeaway:
Path-based problems follow a DFS + backtracking skeleton. Recognize whether the path is root-to-leaf, any-node-to-any-node, or sum-based, and apply the template accordingly.

Top comments (0)