CODEWITHSUNDEEP
c++algorithmtreebinary-treebinary-search
user1002288
user1002288

Reputation: 5040

Given a binary search tree and a number, find a path whose node's data added to be the given number.

Given a binary search tree and a number, find if there is a path from root to a leaf such that all numbers on the path added up to be the given number.

I know how to do it by recursively. But, I prefer an iterative solution.

If we iterate from root to a leaf each time, there will be overlap because some paths may have overlap.

What if the tree is not binary search ?

Thanks

Upvotes: 0

Views: 875

Answers (3)

suat
suat

Reputation: 4289

For BST:

Node current,final = (initialize)
List nodesInPath;
nodesInPath.add(current);
while(current != final) {
    List childrenNodes = current.children;
    if(noChildren) noSolution;
    if(current < final) {
        //choose right child if there is one, otherwise no solution
        current = children[right];
    } else if(current > final){
        //choose left child if there is one, otherwise no solution
        current = children[left];         
    } 
    nodesInPath.add(current);
}
check sum in the nodesInPath

However, for non BST you should apply a solution using dynamic programming as derekhh suggests if you don't want to calculate same paths over and over again. I think, you can store the total length between a certain processed node and the root node. You calculate the distances when you expand them. Then you would apply Breadth-first search to not to traverse same paths again and use previously computed total distances. The algorithm comes to my mind is a little complex, sorry but not have enough time to write it.

Upvotes: 0

derekhh
derekhh

Reputation: 5542

Basically this problem can be solved using Dynamic Programming on tree to avoid those overlapping paths.

The basic idea is to keep track of the possible lengths from each leaf to a given node in a table f[node]. If we implement it in a 2-dimensional boolean array, it is something like f[node][len], which indicates whether there is a path from a leaf to node with length equal to len. We can also use a vector<int> to store the value in each f[node] instead of using a boolean array. No matter what kind of representation you use, the way you calculate between different f are straightforward, in the form of

f[node] is the union of f[node->left] + len_left[node] and f[node->right] + len_right[node].

This is the case of binary tree, but it is really easy to extend it to non-binary-tree cases.

If there is anything unclear, please feel free to comment.

Upvotes: 1

tskuzzy
tskuzzy

Reputation: 36476

Anything you can do recursively, you can also do iteratively. However you are not having performance issues with the recursive solution, then I would leave it as is. It would more likely than not be more difficult to code/read if you try to do it iteratively.

However if you insist, you can transform your recursive solution into an iterative one by using a stack. Every time you make a recursive call, push the state variables in your current function call onto the stack. When you are done with a call, pop off the variables.

Upvotes: 0

Related Questions