Do you think IIT Guwahati certified course can help you in your career?
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.
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
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".
Two Pointer Approach
To minimize time complexity, we bring two pointer approach into use.
Discussing the optimized approach.
First, write a function that gives the inorder traversal for both the BST.
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.
Write if condition(arr1[i]+arr2[j]==X) to check if the given condition is satisfied.
If the condition is not satisfied, use the binary search method to move iterators.
Else if arr1[i] + arr2[j] > X decrement j.
Else if arr1[i] + arr2[j] < X increment i.
Algorithm
Traverse the first BST in inorder using the ‘inorder’ function and store the values in array ‘arr1’.
Traverse the second BST in inorder using the ‘inorder’ and store the values in array ‘arr2’.
Initialize i with the first index of arr1 and j with the last index of ‘arr2’.
While i<n and j<m (n and m are the sizes of the array)
If arr1[i]+arr2[j] == X return true.
Else if arr1[i] + arr2[j] > X decrement j.
Else if arr1[i] + arr2[j] < X increment i.
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.
Now, we see arr1[i]+arr2[j] = 19, which is greater than X. Decrement j.
Now arr[i]+arr[j] = 16, which is again greater than 14. Again decrement j.
Now we see arr[i] + arr[j] =15, which is again greater than 14. Therefore we again decrement j.
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;
}
You can also try this code with Online C++ Compiler
# 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")
You can also try this code with Online Python Compiler
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
Define a function called "existsPair" that takes in three arguments:
root1 - a pointer to the root node of the first BST
root2 - a pointer to the root node of the second BST
X - an integer value representing the target sum
Create two stacks called "stack1" and "stack2" to store nodes for the forward and backward iterators, respectively.
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.
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.
Use the two-pointer technique to traverse through the BSTs:
Set "val1" to the data value of the top node of "stack1" and "val2" to the data value of the top node of "stack2".
If "val1" + "val2" equals the "X", return true.
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.
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.
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.
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.
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
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.
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.
Now, 14 is added into the stack.
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.
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;
}
You can also try this code with Online C++ Compiler
# 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")
You can also try this code with Online Python Compiler
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.
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:
84+ registered