Table of contents
1.
Introduction
1.1.
Binary tree
1.2.
Problem Statement
1.3.
Some Examples
2.
Approach
2.1.
Algorithm
2.2.
Code in C++
2.2.1.
Complexity Analysis 
3.
Frequently asked questions
3.1.
What is an AVL tree?
3.2.
What is postorder traversal in a binary tree?
3.3.
What is the time complexity of insertion, deletion, and updation of an element from the unordered_map of C++?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find if there is a pair in root to a leaf path with a sum equal to the root's data

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

The binary tree is one of the most important topics required for interview preparation. Many companies, including the MAANG, ask questions from binary trees in the technical rounds and interviews. Since this topic is important, it becomes necessary to practice it thoroughly. 

To help you solve problems on binary trees, we will be discussing a simple problem of binary trees. The problem is to find if there is a pair in root to a leaf path with a sum equal to the root's data. But before discussing the problem, let's first understand what a binary tree is.

Binary tree

A binary tree is a tree data structure in which each node has at most two children, which are known as the left and right children.

Each node in a binary tree has a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the tree's topmost node. The left and right pointers point to smaller "subtrees" on either side. A null pointer symbolizes the empty tree, a binary tree with no children.

Problem Statement

Ninjas have a binary tree. The binary tree has n nodes in it. He gave the binary tree to us and said that we have to find if there is a pair in root to a leaf path with a sum equal to the root's data. But, the problem is that he cannot find the pair by himself he is busy with some other work. Can you help him with the problem?

You need to print Yes if there is pair in root to a leaf path with a sum equal to the root's data. Else, print No.

Before deep-diving into the solution to this problem, we should look at some examples to help us understand the problem better. 

Some Examples

Input:

Tree: 

Output: 

Yes
You can also try this code with Online C++ Compiler
Run Code


Explanation:

The root to a leaf path {9,3,6} consists of the pair {3,6} whose sum is equal to 9, equal to the root's value.

Input:

Tree:

 

Output:

No
You can also try this code with Online C++ Compiler
Run Code

 

Explanation:

There is no root to a leaf path having a pair with a sum equal to the root's data.

Approach

The approach to solving this problem of finding a pair in root to a leaf path with a sum equal to the root's data is quite straightforward. In this approach, we will store every node's value in the map. And at every point, we will check if a value is equal to (rootValue-currentNode) in the map. If it exists, we will return true else; continue. We will return false if we reach any node having a NULL value.

Algorithm

1. To solve this problem, we will create a boolean function called doesPairExist(), and in the main function, we will make two function calls for this function, one for the left subtree and another for the right subtree.

2. While traversing the tree, we will return false if the node becomes NULL.

3. We will check for the following condition:

   if (m.find(rootValue - root->data) != m.end())
          return true;
You can also try this code with Online C++ Compiler
Run Code


4. Here root value is the value of the root node, and the root->data is the value of the current node of the tree.

5. Now, we will increment the current node's value in the map.

6. After incrementing the current node's value, we will make two recursive calls.

   // checking for left subtree
   bool left = doesPairExist(root->left, m, rootValue);

   // check for right subtree
   bool right = doesPairExist(root->right, m, rootValue);
You can also try this code with Online C++ Compiler
Run Code


7. After making these two recursive calls, we will decrease the current node's value from the map. 

8. In the end, we will return the OR value of the left and right. So that if one of the calls returns true, we will return true to the main function.

Code in C++

// C++ code to find if there is a pair in root to a leaf path with a sum equal to the root’s data
#include <bits/stdc++.h>
using namespace std;

struct Tree
{
   int data;
   Tree *left;
   Tree *right;
   Tree(int x) : data(x), left(NULL), right(NULL) {}
};

bool doesPairExist(Tree *root, unordered_map<int, int> m, int rootValue)
{
   if (!root)
      return false;

   // check if there exist any node having value equal to (rootValue - root->data)
   if (m.find(rootValue - root->data) != m.end())
      return true;

   // incrementing the current node's value
   m[root->data]++;

   // checking for left subtree
   bool left = doesPairExist(root->left, m, rootValue);

   // check for right subtree
   bool right = doesPairExist(root->right, m, rootValue);

   // decrementing the current node's value
   m[root->data]--;

   // if any of the subtrees consist of a pair then return the OR value
   return left | right;
}

int main()
{
   Tree *root = new Tree(9);
   root->left = new Tree(5);
   root->right = new Tree(7);
   root->right->left = new Tree(9);
   root->right->right = new Tree(12);
   root->left->left = new Tree(4);
   root->left->right = new Tree(8);
   root->left->left->left = new Tree(10);

   // to store the frequencies of values of every node
   unordered_map<int, int> m;

   // check if the left subtree or right subtree contains any pair in there root to leaf path
   if (doesPairExist(root->left, m, root->data) | doesPairExist(root->right, m, root->data))
   {
      cout << "Yes" << endl;
   }
   else
   {
      cout << "No" << endl;
   }
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

Yes

 

Complexity Analysis 

Since we are performing the preorder traversal to find a pair, the time complexity would be O(N), where N would be the number of nodes present in the tree.

Since we are using extra space as an unordered map, we are storing the node's value in the map. Therefore the space complexity is O(N).

Check out this problem - Pair Sum In Array.

Frequently asked questions

What is an AVL tree?

AVL trees are height-balancing binary search trees. It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. The AVL tree checks the left and right subtrees' heights and ensures the difference is less than one. This distinction is referred to as the Balance Factor. This allows us to search the AVL tree in O(log n) time, where n is the number of nodes in the tree.
 

What is postorder traversal in a binary tree?

In the preorder traversal of a tree, we always process the left subtree of the root first, then we process the right subtree of the root, and in the end, we process the root. 

The order looks like this:

left-->right-->root

What is the time complexity of insertion, deletion, and updation of an element from the unordered_map of C++?

The average case time complexity of insertion, deletion, and updation of an element in an unordered_map is O(1). 

Conclusion

In this article, we have discussed the problem of finding a pair in root to a leaf path with a sum equal to the root's data. We discussed the approach to solve this problem and saw its implementation in C++. In the end, we have discussed the approach's time and space complexities.

We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve it and try some new and different approaches. 

If you want to practice problems on binary trees, you can refer to these links:

  1. Tree Traversals
  2. Binary Tree Pruning
  3. Left View Of Binary Tree
  4. Is Height Balanced Binary Tree

 

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDatabase Management Systems, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding.

Live masterclass