binary tree

[jackel7777]

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

bool find(Node* node, int sum)
{
if (!node)
return false;
else if (sum-node->value==0){
cout<<node->value;
return true;
}
else{
bool found=false;
if (find(node->left, sum-node->value)){
cout<<node->value;
found=true;
}
if(find(node->right, sum-node->value)){
cout<<node->value;
found=true;
}
return found;
}
}

void traverse(Node* node, int sum){
if (!node)
return ;
find(node, sum);
traverse(node->left, sum);
traverse(node->right, sum);
}

int main(){
traverse(root, 100);
}

This solution to me has a complexity of O(n^2lgn).Can thisbe done in O(lgn)?

[ne555]

Design an algorithm to print all paths which sum up to that value

You need to traverse every node to be sure that it is or not a path. So the complexity can't be lower than O(n).

About your algorithm.
Starting in every node you traverse all the tree that has that node as root. In a balanced tree that means one half of the number that the parent has.
n + 2 * n/2 + 4 *n/4 + ...
But you only have lg(n) levels, where every level adds up to n, so your complexity is O(n lg(n) )

I dunno how to improve that. Besides, how many paths there are (as a function of n)?

[jsmith]

Must the path end at a leaf, or can it end anywhere in the tree?

[zwA4jE8b]

http://en.wikipedia.org/wiki/Binary_search_tree

this is representative of what I learned in class.

The worst case for a bst is that it degenerates into a linked list, which is O(n).

[jackel7777]

it can be anywhere in the tree