ks4394
BAN USER- 0of 0 votes
AnswersThe question: given a binary tree, print all paths that sum to a certain value.
I've come up with the following approach (C++). This is different from other solutions I found on the web, that search the path list every time. I would appreciate your opinion regarding my attempt.
- ks4394 in United States// Main function void print_path_with_sum(Node* root, int expected_sum) { if (!root) return; std::vector<Node*> path; search_to_bottom(root, path, 0, expected_sum); print_path_with_sum(root->left, expected_sum); print_path_with_sum(root->right, expected_sum); } // Helper function void search_to_bottom(Node* node, std::vector<Node*>& path, int current, int expected_sum) { if (!node) return; current += node->value; path.push_back(node); if (current == expected_sum) { print_path(path, 0, path.size()); } search_to_bottom(node->left, path, current, expected_sum); search_to_bottom(node->right, path, current, expected_sum); path.pop_back(); }
| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm
joe kidd, thanks for your response. Apparently you missed that fact that the main function (print_path_with_sum) calls the inner function (search_to_bottom) for EVERY node in the tree. So it will find other paths than those starting at the root.
I know the solution from the Cracking the Coding Interview book, I just wanted to present my approach and get some opinions.
Running on some sample data, it seems that my function visits fewer nodes than the book's solution. But they are probably equal in the worst case.
The naive approach would just compare each row to all other rows. This requires O(n*n*m) time and O(1) space.
- ks4394 September 10, 2013A better approach would be to use a hash table. For each row we compute the hash value of it, and check if it exists in the table. This requires O(n*m) time and O(n) space.
This approach has a problem with collisions. If the hash value already exists in the table, we must check if the rows are actually equal (or their has value collide), so this affects the time complexity.
Here is an implementation of this approach in C++: coliru.stacked-crooked.com/a/7a47232f32677be5
Is there a better approach in terms of time or space complexity?