[Trees and Graphs] interview questions #12

[rygh4775]

Paths with Sum: You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

[rygh4775]

Approach

Recursive DFS

Solution

int countTotalWays(TreeNode root, int toBeSum) {
    if(root == null) return 0;

    int waysFromRoot = countWays(root, 0, toBeSum);
    int waysFromLeft = countTotalWays(root.left, toBeSum);
    int waysFromRight = countTotalWays(root.right, toBeSum);

    return waysFromRoot + waysFromLeft + waysFromRight;
}

void countWays(TreeNode node, int sum, int toBeSum) {
    if(node == null) return 0;

    int ways = 0;
    sum += node.data;
    if(sum == toBeSum) {
        ways++;
    }
    ways += countWays(node.left, sum, toBeSum);
    ways += countWays(node.right, sum, toBeSum);

    return ways;
}

Time complexity

O(NlogN), N is the number of tree nodes

Space complexity

O(N), N is the number of tree nodes