Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example 
3.
Two Pointer Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Code in C++
3.4.
Code in Python
3.5.
Complexity
4.
Optimized Approach
4.1.
Algorithm 
4.2.
Dry Run
4.3.
Code in C++
4.4.
Code in Python
4.5.
Complexity
5.
Frequently Asked Questions
5.1.
What is a binary search tree?
5.2.
What is the advantage of BST over the binary tree? 
5.3.
What is inorder traversal?
5.4.
What is a root Node?
5.5.
What is a child Node?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Check for Nodes from given two BSTs with a sum equal to X

Author Rishabh Singh
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This blog will address a common interview question that involves binary search trees. It is crucial to have a strong grasp of recursion before attempting any BST problems. First, let's understand what a Binary Search Tree is.

Introduction image

A Binary Search Tree is a binary tree in which the value of the left child is less than the value of the parent, while the value of the right child is greater than the value of the parent. Every subtree of the BST must adhere to this rule. This blog will also provide a comprehensive analysis of the problem.

Problem Statement

We are given two binary search trees and a sum; we need to find two nodes taken each from the given two BST and check if there are two nodes whose sum equals the given input sum. We need to print ‘Yes’ if such two nodes exist, or else print ‘No’.

Example 

Input 

Input example

X=14

Output

Yes

Explanation

  • First, we can take 4 from the first BST and look for 10 in the second BST in order to get the sum 14. We can find 10 from the second BST. Hence the sum would be 14.
     
  • We can also take 2 from the first BST and look for 12 in the second BST in order to get the sum 14. We can find 12 from the second BST. Again the sum would be 14.
     
  • We can also take 1 from the first BST and look for 13 in the second BST in order to get the sum 14. We can find 13 from the second BST. Again the sum would be 14.
     
  • We can also take 9 from the first BST and look for 5 in the second BST in order to get the sum 14. We can find 5 from the second BST. Again the sum would be 14.
     
  • Therefore output will be "Yes".
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Two Pointer Approach

To minimize time complexity, we bring two pointer approach into use.

Discussing the optimized approach.

  1. First, write a function that gives the inorder traversal for both the BST.
     
  2. Write a function to check if there exists a pair such that the given sum is equal to the sum of the pair taken from two BSTs.
     
  3. Write if condition(arr1[i]+arr2[j]==X) to check if the given condition is satisfied.
     
  4. If the condition is not satisfied, use the binary search method to move iterators.
    1. Else if arr1[i] + arr2[j] > X decrement j.
       
    2. Else if arr1[i] + arr2[j] < X increment i.

Algorithm

  1. Traverse the first BST in inorder using the ‘inorder’ function and store the values in array ‘arr1’.
     
  2. Traverse the second BST in inorder using the ‘inorder’ and store the values in array ‘arr2’.
     
  3. Initialize i with the first index of arr1 and j with the last index of ‘arr2’.
     
  4. While i<n and j<m (n and m are the sizes of the array)
    1. If arr1[i]+arr2[j] == X return true.
    2. Else if arr1[i] + arr2[j] > X decrement j.
    3. Else if arr1[i] + arr2[j] < X increment i.
       
  5.  If we have reached the end of any one array and didn’t find the pair return false.

Dry Run

  • Start by making an inorder traversal of both the BST with ‘i’ at the first index of BST1 and ‘j’ at the last index of BST2. The value of ‘X’ is 14. 
Step 1
  • Now, we see arr1[i]+arr2[j] = 19, which is greater than X. Decrement j.
Step 2
  • Now arr[i]+arr[j] = 16, which is again greater than 14. Again decrement j.
Step 3
  • Now we see arr[i] + arr[j] =15, which is again greater than 14. Therefore we again decrement j. 
Step 4
  • Now we see arr[i] + arr[j] =14, which was the given value of X. Hence, return true.

Code in C++

#include <iostream>
using namespace std;

// A binary tree node.
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = right = NULL;
    }
};

// Inorder traversal of a BST.
void inorder(Node* root, int arr[], int& index) {
    // if root is null then return 
    if (root == NULL) {
        return;
    }
    // traverse the left subtree recursively
    inorder(root->left, arr, index);
    // visit the current node 
    arr[index++] = root->data;
    // traverse the right subtree recursively
    inorder(root->right, arr, index);
}

// Check if the sum of two nodes equals the given sum.
bool existsPair(int arr1[], int size1, int arr2[], int size2, int x) {
    int i = 0, j = size2 - 1;
    while (i < size1 && j >= 0) {
        // if the sum of nodes equals sum return true
        if (arr1[i] + arr2[j] == x) {
            return true;
        } 
        // if the sum of nodes is less than sum increment i
        else if (arr1[i] + arr2[j] < x) {
            i++;
        } 
        // if the sum of nodes is more than sum decrement j
        else {
            j--;
        }
    }
    return false;
}

// Driver code.
int main() {
    // First BST.
    Node* root1 = new Node(4);
    root1->left = new Node(2);
    root1->right = new Node(7);
    root1->left->left = new Node(1);
    root1->left->right = new Node(3);
    root1->right->left = new Node(6);
    root1->right->right = new Node(9);

    // Second BST.
    Node* root2 = new Node(13);
    root2->left = new Node(10);
    root2->right = new Node(15);
    root2->left->left = new Node(5);
    root2->left->right = new Node(12);
    root2->right->left = new Node(14);
    root2->right->right = new Node(18);

    // Arrays to store inorder traversal of BSTs.
    int arr1[7], arr2[7];
    int index1 = 0, index2 = 0;

    // Perform inorder traversal of both BSTs.
    inorder(root1, arr1, index1);
    inorder(root2, arr2, index2);

    // Given sum.
    int x = 14;
    // calling the function to check if pair exists 
    if (existsPair(arr1, index1, arr2, index2, x)) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}


Output 

Cpp output

Code in Python

# A binary tree node.
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
# Inorder traversal of a BST.
def inorder(root, arr, index):
    # if root node is null then return 
    if root is None:
        return
    # traverse the left subtree recursively
    inorder(root.left, arr, index)
    # visit the current node  
    arr[index[0]] = root.data
    index[0] += 1
    # traverse the right subtree recursively
    inorder(root.right, arr, index)

# Check if the sum of two nodes equals the given sum.
def existsPair(arr1, size1, arr2, size2, x):
    # initialize i and j for the two arrays 
    i, j = 0, size2 - 1
    while i < size1 and j >= 0:
        # if the sum of nodes equals given sum return true
        if arr1[i] + arr2[j] == x:
            return True
        # if the sum of nodes is less than given sum increment i
        elif arr1[i] + arr2[j] < x:
            i += 1
        # if the sum of nodes is more than given sum decrement j
        else:
            j -= 1
    return False

# Driver code.
if __name__ == '__main__':
    # First BST.
    root1 = Node(4)
    root1.left = Node(2)
    root1.right = Node(7)
    root1.left.left = Node(1)
    root1.left.right = Node(3)
    root1.right.left = Node(6)
    root1.right.right = Node(9)

    # Second BST.
    root2 = Node(13)
    root2.left = Node(10)
    root2.right = Node(15)
    root2.left.left = Node(5)
    root2.left.right = Node(12)
    root2.right.left = Node(14)
    root2.right.right = Node(18)

    # Arrays to store the inorder traversal of BSTs.
    arr1, arr2 = [0] * 7, [0] * 7
    index1, index2 = [0], [0]

    # Perform the inorder traversal of both BSTs.
    inorder(root1, arr1, index1)
    inorder(root2, arr2, index2)

    # Given sum.
    x = 14
    # check if a pair exists and print result 
    if existsPair(arr1, index1[0], arr2, index2[0], x):
        print("Yes")
    else:
        print("No")


Output 

Python Output

Complexity

Time Complexity O(M+N).

The time complexity is O(M+N) because the while loop that finds the pair with sum X takes O(M + N) time, where ‘M’ represents the size of the first array, whereas 'N' represents the size of the second array obtained from the inorder traversals.

Space Complexity O(M+N).

The space complexity is O(M + N), where ‘M’ is the number of nodes in the first BST and ‘N’ represents the number of nodes in the second BST because we are storing the inorder traversal of both the BSTs.

Optimized Approach

This approach involves using two iterators initialized by the smallest and largest nodes, respectively. The iterators move towards each other while checking the sum of the values of the nodes they point to until they meet or the sum is greater than the target sum. The two-pointer technique helps reduce the search time by discarding irrelevant nodes. A stack is used to store nodes visited during iteration.

Algorithm 

  1. Define a function called "existsPair" that takes in three arguments:

    1. root1 - a pointer to the root node of the first BST
       
    2. root2 - a pointer to the root node of the second BST
       
    3. X - an integer value representing the target sum
       
  2. Create two stacks called "stack1" and "stack2" to store nodes for the forward and backward iterators, respectively.
     
  3. Initialize the forward iterator for the first BST by setting "curr" to "root1" and pushing all the left nodes of "curr" onto "stack1" until "curr" is null.
     
  4. Initialize the backward iterator for the second BST by setting "curr" to "root2" and pushing all the right nodes of "curr" onto "stack2" until "curr" is null.
     
  5. Use the two-pointer technique to traverse through the BSTs:

    1. Set "val1" to the data value of the top node of "stack1" and "val2" to the data value of  the top node of "stack2".
       
    2. If "val1" + "val2" equals the "X", return true.
       
    3. If "val1" + "val2" is less than the "X", move the forward iterator one step to the right by setting "curr" to the right child of the top node of "stack1" and pop the top node from "stack1". Then, push all the left nodes of "curr" onto "stack1" until "curr" is null.
       
    4. If "val1" + "val2" is greater than the "X", move the backward iterator one step to the left by setting "curr" to the left child of the top node of "stack2" and pop the top node from "stack2". Then, push all the right nodes of "curr" onto "stack2" until "curr" is null.
       
  6. If no such pair is found, return false.

Dry Run

  • First, the function existsPair is called with the root nodes of the two BSTs and the target sum X=14.
First and Second BST
  • Then, two stacks stack1 and stack2 are initialized to store nodes for forward and backward iterator, respectively.

    • The forward iterator is initialized for the first tree by pushing nodes into stack1 starting from the root node and moving left until there are no more left children. Here, we have pushed 4, 2 and 1 to stack1. 
Stack 1
  • Similarly, the backward iterator is initialized for the second tree by pushing nodes into stack2, starting from the root node and moving right until there are no more right children. Here, we have pushed 13, 15 and 18 to stack2
Stack 2
  • Then, a two-pointer technique is used to iterate through the nodes in the two trees. At each step, the top nodes of stack1 and stack2 are popped and their values are stored in val1 and val2, respectively.
  • If val1 + val2 == X, a valid pair is found and the function returns true. 
     
  • Else  if, val1 + val2 < X, the forward iterator of the first tree is moved to the right value of the top element.
     
  • Else,  val1 + val2 > X, the backward iterator of the second tree is moved to the left value of the top element.
     
  • Here, val1 is the top element of stack1 and val2 is the top element of stack2.
  • val1 = 1  val2=18
     
  • Here, val1+val2 = 19. 19>14 (which was the given value of X).
     
  • Since val1+val2 > X, the backward iterator of the second tree is moved to the left value of the top element and the top element (i.e., 18) is popped out of the stack.
     
  • Here the left value of the top element is NULL. So we do not add any element to the stack. 
Two pointer approach 1
  • Now, the new top node of stack2 is 15. 
  • val1 = 1  val2 = 15
     
  • Here, val1+val2 = 16. 16>14 (which was the given value of X).
     
  • Since, val1+val2 > X the backward iterator of the second tree is moved to the left of the top element and the top element (i.e., 15) is popped out of the stack.
     
  • After popping 15, the left of the top element is 14. So we add 14 to the stack.
Two pointer approach 2
  •  Now, 14 is added into the stack.
Two pointer approach 3
  • With, 14 being the new top element of the stack.
  • val1=1  val2=14
     
  • val1+val2 = 15. 15>14 (which was the given value of X).
     
  • Since val1+val2 > X, the backward iterator of the second tree is moved to the left value of the top element and the top element (i.e., 14) is popped out of the stack.
     
  • Here, the left value is NULL. So we do not add any element to the stack. 
Two pointer approach 4
  • Now, val1 is still 1, but val2 is 13. val1+val2 = 14, which is the required value of X. Hence, the function returns “true”.

Code in C++

#include <iostream>
#include <stack>
using namespace std;

// Node of the binary tree
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = right = NULL;
    }
};

// Function to initialize the forward iterator for a given tree
void initializeForwardIterator(Node* root, stack<Node*>& stack) {
    Node* curr = root;
    while (curr != NULL) {
        stack.push(curr);
        curr = curr->left;
    }
}

// Function to initialize the backward iterator for a given tree
void initializeBackwardIterator(Node* root, stack<Node*>& stack) {
    Node* curr = root;
    while (curr != NULL) {
        stack.push(curr);
        curr = curr->right;
    }
}

// Function that checks if a pair exists or not
bool existsPair(Node* root1, Node* root2, int X) {
    stack<Node*> stack1, stack2;

    // Initializing the forward iterator for the first tree
    initializeForwardIterator(root1, stack1);

    // Initializing the backward iterator for the second tree
    initializeBackwardIterator(root2, stack2);

    // Two pointer technique
    while (!stack1.empty() && !stack2.empty()) {
        // Store the top values of both the stacks 
        int val1 = stack1.top()->data;
        int val2 = stack2.top()->data;

        // If pair is found
        if (val1 + val2 == X)
            return true;

        // If sum is less than X move forward iterator
        if (val1 + val2 < X) {
            Node* curr = stack1.top()->right;
            stack1.pop();
            initializeForwardIterator(curr, stack1);
        }
        // If the sum is more than X move forward iterator
        else {
            Node* curr = stack2.top()->left;
            stack2.pop();
            initializeBackwardIterator(curr, stack2);
        }
    }
    // If no such pair found
    return false;
}

// Driver code
int main() {
     // First BST.
    Node* root1 = new Node(4);
    root1->left = new Node(2);
    root1->right = new Node(7);
    root1->left->left = new Node(1);
    root1->left->right = new Node(3);
    root1->right->left = new Node(6);
    root1->right->right = new Node(9);

    // Second BST.
    Node* root2 = new Node(13);
    root2->left = new Node(10);
    root2->right = new Node(15);
    root2->left->left = new Node(5);
    root2->left->right = new Node(12);
    root2->right->left = new Node(14);
    root2->right->right = new Node(18);

    // Set X
    int x = 14;

    if (existsPair(root1, root2, x))
        cout << "Yes";
    else
        cout << "No";

    return 0;
}


Output

 Cpp Output

Code in Python

# Node of the binary tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to initialize the forward 
# iterator for a given tree
def initializeForwardIterator(root, stack):
    curr = root
    while curr != None:
        stack.append(curr)
        curr = curr.left

# Function to initialize the backward
# iterator for a given tree
def initializeBackwardIterator(root, stack):
    curr = root
    while curr != None:
        stack.append(curr)
        curr = curr.right

# Function that checks if a pair exists or not
def existsPair(root1, root2, X):
    stack1, stack2 = [], []

    # Initializing forward iterator for the first tree
    initializeForwardIterator(root1, stack1)

    # Initializing backward iterator for the second tree
    initializeBackwardIterator(root2, stack2)

    # Two pointer technique
    while stack1 and stack2:
        # Store the top values of both the stacks
        val1 = stack1[-1].data
        val2 = stack2[-1].data

        # If pair is found
        if val1 + val2 == X:
            return True

        # If sum is less than X move the forward iterator
        if val1 + val2 < X:
            curr = stack1[-1].right
            stack1.pop()
            initializeForwardIterator(curr, stack1)
        # If sum is more than X move the backward iterator
        else:
            curr = stack2[-1].left
            stack2.pop()
            initializeBackwardIterator(curr, stack2)

    # If no such pair found
    return False

# Driver code
if __name__ == "__main__":
    # First BST.
    root1 = Node(4)
    root1.left = Node(2)
    root1.right = Node(7)
    root1.left.left = Node(1)
    root1.left.right = Node(3)
    root1.right.left = Node(6)
    root1.right.right = Node(9)

    # Second BST.
    root2 = Node(13)
    root2.left = Node(10)
    root2.right = Node(15)
    root2.left.left = Node(5)
    root2.left.right = Node(12)
    root2.right.left = Node(14)
    root2.right.right = Node(18)

    # Set X
    X = 14

    if existsPair(root1, root2, X):
        print("Yes")
    else:
        print("No")


Output

 Python output

Complexity

Time Complexity = O(M+N)

The time complexity is O(M+N), where M is the number of nodes in the first BST and N is the number of nodes in the second BST. This is because the function traverses both trees in a single pass, using two iterators and a two-pointer technique, without revisiting any nodes.

Space Complexity = O(H1+H2)

The space complexity of the ‘existsPair’ function is O(H1 + H2), where H1 and H2 are the heights of the two given BSTs. This is because the function uses two stacks to keep track of the iterators for the two trees. The maximum size of each stack is equal to the height of the corresponding tree. Therefore, the space used by the function depends on the heights of the two trees, and it can be worst-case O(N) if the trees are skewed.

Check out this problem - Pair Sum In Array.

Frequently Asked Questions

What is a binary search tree?

A binary tree whose value of the left node is smaller than the root node and the right node value is greater than the root node.

What is the advantage of BST over the binary tree? 

Binary trees are slower in some operations, such as insertion, searching, and deletion, due to their unordered nature.

What is inorder traversal?

 Inorder traversal refers to processing the left subtree, root, and right subtree.

What is a root Node?

A root node is the starting node of the tree.

What is a child Node?

A child node is a node that is directly connected to its parent node through an edge or link.

Conclusion

In this blog, we learned how to check for nodes from given two BSTs with a sum equal to X. We have implemented the problem in C++ programming language.

For more Tree data structure articles, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Convert a Sorted Linked List to Balanced BST
Next article
Count Number of Subsets With Given Sum
Live masterclass