Given a binary tree, find if there is a pair in root to a leaf path such that sum of values in pair is equal to root’s data. For example, in below tree (2, 3) and (4, 1) are pairs with sum equals to root’s data.
The idea is based on hashing and tree traversal. The idea is similar to method 2 of array pair sum problem.
- Create an empty hash table.
- Start traversing tree in Preorder fashion.
- If we reach a leaf node, we return false.
- For every visited node, check if root’s data minus current node’s data exists in hash table or not. If yes, return true. Else insert current node in hash table.
- Recursively check in left and right subtrees.
- Remove current node from hash table so that it doesn’t appear in other root to leaf paths.
Below is the implementation of above idea.
Time Complexity: O(n) under the assumption that hash search, insert and erase take O(1) time.
Exercise : Extend the above solution to print all root to leaf paths that have a pair with sum equals to root’s data.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.