Root to leaf paths sum

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Sum of numbers formed by root-to-leaf paths (each path represents a number).

Algorithm

1DFS: pass current number = prev * 10 + node.val. At leaf: add to total sum.

Common Pitfalls

•Same as LC 129. Accumulate number at each level. Sum all leaf values.

Root to leaf paths sum.java

Java

// Approach: DFS. Accumulate all root-to-leaf path sums as numbers; return total.
// Time: O(n) Space: O(h)
class Tree {
    int data;
    Tree left, right;

    Tree(int d) {
        data = d;
        left = null;
        right = null;
    }
}

class Solution {
    public static int treePathsSum(Node root) {
        return dfs(root, 0);
    }

    private static int dfs(Node node, int val) {
        if (node == null)
            return 0;

        val = val * 10 + node.data;
        if (node.left == null && node.right == null)
            return val;

        return dfs(node.left, val) + dfs(node.right, val);
    }
}

Was this solution helpful?