Find if there is a pair in root to a leaf path with sum equals to root's data - GeeksforGeeks

Find if there is a pair in root to a leaf path with sum equals to root's data - GeeksforGeeks
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.

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.

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);

}

Read full article from Find if there is a pair in root to a leaf path with sum equals to root's data - GeeksforGeeks