Finds the path from root node to given root of the tree, Stores the path in a vector path[], returns true if path exists otherwise false
| 24 | // Finds the path from root node to given root of the tree, Stores the |
| 25 | // path in a vector path[], returns true if path exists otherwise false |
| 26 | bool findPath(Node *root, vector<int> &path, int k) |
| 27 | { |
| 28 | // base case |
| 29 | if (root == NULL) return false; |
| 30 | |
| 31 | // Store this node in path vector. The node will be removed if |
| 32 | // not in path from root to k |
| 33 | path.push_back(root->key); |
| 34 | |
| 35 | // See if the k is same as root's key |
| 36 | if (root->key == k) |
| 37 | return true; |
| 38 | |
| 39 | // Check if k is found in left or right sub-tree |
| 40 | if ( (root->left && findPath(root->left, path, k)) || |
| 41 | (root->right && findPath(root->right, path, k)) ) |
| 42 | return true; |
| 43 | |
| 44 | // If not present in subtree rooted with root, remove root from |
| 45 | // path[] and return false |
| 46 | path.pop_back(); |
| 47 | return false; |
| 48 | } |
| 49 | |
| 50 | // Returns LCA if node n1, n2 are present in the given binary tree, |
| 51 | // otherwise return -1 |