Find if there is a pair in root to a leaf path with sum equals to root’s data
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 there are no pairs in any root to leaf path with sum equal 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.
C++
// C++ program to find if there is a pair in any root // to leaf path with sum equals to root's key. #include<bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; struct Node* left, *right; }; /* utility that allocates a new node with the given data and NULL left and right pointers. */ struct Node* newnode( int data) { struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } // Function to print root to leaf path which satisfies the condition bool printPathUtil(Node *node, unordered_set< int > &s, int root_data) { // Base condition if (node == NULL) return false ; // Check if current node makes a pair with any of the // existing elements in set. int rem = root_data - node->data; if (s.find(rem) != s.end()) return true ; // Insert current node in set s.insert(node->data); // If result returned by either left or right child is // true, return true. bool res = printPathUtil(node->left, s, root_data) || printPathUtil(node->right, s, root_data); // Remove current node from hash table s.erase(node->data); return res; } // A wrapper over printPathUtil() bool isPathSum(Node *root) { // create an empty hash table unordered_set< int > s; // Recursively check in left and right subtrees. return printPathUtil(root->left, s, root->data) || printPathUtil(root->right, s, root->data); } // Driver program to run the case int main() { struct Node *root = newnode(8); root->left = newnode(5); root->right = newnode(4); root->left->left = newnode(9); root->left->right = newnode(7); root->left->right->left = newnode(1); root->left->right->right = newnode(12); root->left->right->right->right = newnode(2); root->right->right = newnode(11); root->right->right->left = newnode(3); isPathSum(root)? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to find if there is a pair in any root // to leaf path with sum equals to root's key. import java.util.*; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left, right; }; /* utility that allocates a new node with the given data and null left and right pointers. */ static Node newnode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } // Function to print root to leaf path which satisfies the condition static boolean printPathUtil(Node node, HashSet<Integer> s, int root_data) { // Base condition if (node == null ) return false ; // Check if current node makes a pair with any of the // existing elements in set. int rem = root_data - node.data; if (s.contains(rem)) return true ; // Insert current node in set s.add(node.data); // If result returned by either left or right child is // true, return true. boolean res = printPathUtil(node.left, s, root_data) || printPathUtil(node.right, s, root_data); // Remove current node from hash table s.remove(node.data); return res; } // A wrapper over printPathUtil() static boolean isPathSum(Node root) { // create an empty hash table HashSet<Integer> s = new HashSet<Integer>(); // Recursively check in left and right subtrees. return printPathUtil(root.left, s, root.data) || printPathUtil(root.right, s, root.data); } // Driver code public static void main(String[] args) { Node root = newnode( 8 ); root.left = newnode( 5 ); root.right = newnode( 4 ); root.left.left = newnode( 9 ); root.left.right = newnode( 7 ); root.left.right.left = newnode( 1 ); root.left.right.right = newnode( 12 ); root.left.right.right.right = newnode( 2 ); root.right.right = newnode( 11 ); root.right.right.left = newnode( 3 ); System.out.print(isPathSum(root)== true ? "Yes" : "No" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find if there is a # pair in any root to leaf path with sum # equals to root's key # A binary tree node has data, pointer to # left child and a pointer to right child """ utility that allocates a new node with the given data and None left and right pointers. """ class newnode: def __init__( self , data): self .data = data self .left = self .right = None # Function to print root to leaf path which # satisfies the condition def printPathUtil(node, s, root_data) : # Base condition if (node = = None ) : return False # Check if current node makes a pair # with any of the existing elements in set. rem = root_data - node.data if rem in s: return True # Insert current node in set s.add(node.data) # If result returned by either left or # right child is True, return True. res = printPathUtil(node.left, s, root_data) or \ printPathUtil(node.right, s, root_data) # Remove current node from hash table s.remove(node.data) return res # A wrapper over printPathUtil() def isPathSum(root) : # create an empty hash table s = set () # Recursively check in left and right subtrees. return printPathUtil(root.left, s, root.data) or \ printPathUtil(root.right, s, root.data) # Driver Code if __name__ = = '__main__' : root = newnode( 8 ) root.left = newnode( 5 ) root.right = newnode( 4 ) root.left.left = newnode( 9 ) root.left.right = newnode( 7 ) root.left.right.left = newnode( 1 ) root.left.right.right = newnode( 12 ) root.left.right.right.right = newnode( 2 ) root.right.right = newnode( 11 ) root.right.right.left = newnode( 3 ) print ( "Yes" ) if (isPathSum(root)) else print ( "No" ) # This code is contributed # by SHUBHAMSINGH10 |
C#
// C# program to find if there is a pair in any root // to leaf path with sum equals to root's key. using System; using System.Collections.Generic; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ public class Node { public int data; public Node left, right; }; /* utility that allocates a new node with the given data and null left and right pointers. */ static Node newnode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } // Function to print root to leaf path // which satisfies the condition static bool printPathUtil(Node node, HashSet< int > s, int root_data) { // Base condition if (node == null ) return false ; // Check if current node makes a pair // with any of the existing elements in set. int rem = root_data - node.data; if (s.Contains(rem)) return true ; // Insert current node in set s.Add(node.data); // If result returned by either left or // right child is true, return true. bool res = printPathUtil(node.left, s, root_data) || printPathUtil(node.right, s, root_data); // Remove current node from hash table s.Remove(node.data); return res; } // A wrapper over printPathUtil() static bool isPathSum(Node root) { // create an empty hash table HashSet< int > s = new HashSet< int >(); // Recursively check in left and right subtrees. return printPathUtil(root.left, s, root.data) || printPathUtil(root.right, s, root.data); } // Driver code public static void Main(String[] args) { Node root = newnode(8); root.left = newnode(5); root.right = newnode(4); root.left.left = newnode(9); root.left.right = newnode(7); root.left.right.left = newnode(1); root.left.right.right = newnode(12); root.left.right.right.right = newnode(2); root.right.right = newnode(11); root.right.right.left = newnode(3); Console.Write(isPathSum(root) == true ? "Yes" : "No" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find if there is a pair in any root // to leaf path with sum equals to root's key. /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { /* utility that allocates a new node with the given data and null left and right pointers. */ constructor(data) { this .data=data; this .left= this .right= null ; } } // Function to print root to leaf path which satisfies the condition function printPathUtil(node,s,root_data) { // Base condition if (node == null ) return false ; // Check if current node makes a pair with any of the // existing elements in set. let rem = root_data - node.data; if (s.has(rem)) return true ; // Insert current node in set s.add(node.data); // If result returned by either left or right child is // true, return true. let res = printPathUtil(node.left, s, root_data) || printPathUtil(node.right, s, root_data); // Remove current node from hash table s. delete (node.data); return res; } // A wrapper over printPathUtil() function isPathSum(root) { // create an empty hash table let s = new Set(); // Recursively check in left and right subtrees. return printPathUtil(root.left, s, root.data) || printPathUtil(root.right, s, root.data); } // Driver code let root = new Node(8); root.left = new Node(5); root.right = new Node(4); root.left.left = new Node(9); root.left.right = new Node(7); root.left.right.left = new Node(1); root.left.right.right = new Node(12); root.left.right.right.right = new Node(2); root.right.right = new Node(11); root.right.right.left = new Node(3); document.write(isPathSum(root)== true ? "Yes" : "No" ); // This code is contributed by rag2127 </script> |
Output
Yes
Time Complexity: O(n) under the assumption that hash search, insert and erase take O(1) time.
Auxiliary Space: O(n)
Exercise : Extend the above solution to print all root to leaf paths that have a pair with sum equals to root’s data.