Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
I think we don't need the list neither the backtracking. We can just do two recu...

Athanasios Petsas

Feb 15, 2022

I think we don't need the list neither the backtracking. We can just do two recursive calls for each child (one passing the sum as is and one with the current node's value subtracted from the sum) in order to cover all the possible cases. So the time and space complexity will be O(N). Sample code in C++:

{code} int pathsWithSum(TreeNode *root, int sum) { int totalPaths = 0; pathsWithSumHelper(root, sum, totalPaths); return totalPaths; }

void pathsWithSumHelper(TreeNode *root, int sum, int & totalPaths) { if (root == nullptr) return;

if (root->val == sum) { totalPaths += 1; }

// we are at a leaf node if (root->left == nullptr && root->right == nullptr) return;

// not leaf pathsWithSumHelper(root->left, sum, totalPaths); pathsWithSumHelper(root->left, sum - root->val, totalPaths); pathsWithSumHelper(root->right, sum, totalPaths); pathsWithSumHelper(root->right, sum - root->val, totalPaths); } {code}

0

0

Comments
Comments
A
Athanasios Petsas4 years ago

actually the if (root->left == nullptr && root->right == nullptr) return; is reduntant..

A
Athanasios Petsas4 years ago

hmm, now that I'm thinking it again, maybe the solution I proposed is wrong, because this way I describe we're going to create also paths that will exclude some intermediate nodes, i.e.n non-continuous which is wrong

A
Alex 4 years ago

You're right that this solution will count paths that incorrectly exclude intermediate nodes. However, I think you can get around that by simply passing a boolean to the recursive implementation that records whether the current call is part of a contiguous path. If you ...

A
Alex 4 years ago

My C# solution with this approach:

public static int CountPaths(TreeNode root, int sum){ return countPathsUtil(root, sum, false); }

private static int countPathsUtil(TreeNode node, int sum, bool onPath){ if(node == null) return 0;

var count = 0;

// increment count ...

On this page