Merge two BSTs with limited extra space
Given two Binary Search Trees(BST), print the inorder traversal of merged BSTs.
Examples:
Input:
First BST
3
/ \
1 5
Second BST
4
/ \
2 6
Output: 1 2 3 4 5 6Input:
First BST
8
/ \
2 10
/
1
Second BST
5
/
3
/
0
Output: 0 1 2 3 5 8 10
Merge two BSTs using Iterative Inorder Traversal:
The idea is to use iterative inorder traversal.
Follow the steps below to solve the problem:
- Consider two stacks s1 and s2 which stores the elements of the two trees.
- Store the left view value of a tree1 in s1 and of tree2 in s2.
- Compare the top values present in the stack and push the value accordingly in the result vector.
- If s2 is empty then pop s1 and put the popped node value in the answer vector
- Else if both s1 and s2 are not empty then compare their top nodes’ value if s1.top()->val <= s2.top()->val then in this case push the s1.top()->val in the result vector and push its right child in the stack s1.
- If s1 is empty then pop s2 and put the popped node value in the answer vector.
- Else if both s1 and s2 are not empty then compare their top nodes’ value if s2.top()->val >= s1.top()->val then in this case push the s2.top()->val in the result vector and push its right child in the stack s2
- Loop while there are nodes not yet printed. The nodes may be in the stack(explored, but not printed) or maybe not yet explored
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Structure of a BST Node class node { public : int data; node* left; node* right; }; //.................... START OF STACK RELATED //STUFF.................... // A stack node class snode { public : node* t; snode* next; }; // Function to add an element k to stack void push(snode** s, node* k) { snode* tmp = new snode(); // perform memory check here tmp->t = k; tmp->next = *s; (*s) = tmp; } // Function to pop an element t from stack node* pop(snode** s) { node* t; snode* st; st = *s; (*s) = (*s)->next; t = st->t; free (st); return t; } // Function to check whether the stack is empty or not int isEmpty(snode* s) { if (s == NULL) return 1; return 0; } //.................... END OF STACK RELATED //STUFF.................... /* Utility function to create a new Binary Tree node */ node* newNode( int data) { node* temp = new node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } /* A utility function to print Inorder traversal of a Binary * Tree */ void inorder(node* root) { if (root != NULL) { inorder(root->left); cout << root->data << " " ; inorder(root->right); } } // The function to print data of two BSTs in sorted order void merge(node* root1, node* root2) { // s1 is stack to hold nodes of first BST snode* s1 = NULL; // Current node of first BST node* current1 = root1; // s2 is stack to hold nodes of second BST snode* s2 = NULL; // Current node of second BST node* current2 = root2; // If first BST is empty, then output is inorder // traversal of second BST if (root1 == NULL) { inorder(root2); return ; } // If second BST is empty, then output is inorder // traversal of first BST if (root2 == NULL) { inorder(root1); return ; } // Run the loop while there are nodes not yet printed. // The nodes may be in stack(explored, but not printed) // or may be not yet explored while (current1 != NULL || !isEmpty(s1) || current2 != NULL || !isEmpty(s2)) { // Following steps follow iterative Inorder // Traversal if (current1 != NULL || current2 != NULL) { // Reach the leftmost node of both BSTs and push // ancestors of leftmost nodes to stack s1 and // s2 respectively if (current1 != NULL) { push(&s1, current1); current1 = current1->left; } if (current2 != NULL) { push(&s2, current2); current2 = current2->left; } } else { // If we reach a NULL node and either of the // stacks is empty, then one tree is exhausted, // print the other tree if (isEmpty(s1)) { while (!isEmpty(s2)) { current2 = pop(&s2); current2->left = NULL; inorder(current2); } return ; } if (isEmpty(s2)) { while (!isEmpty(s1)) { current1 = pop(&s1); current1->left = NULL; inorder(current1); } return ; } // Pop an element from both stacks and compare // the popped elements current1 = pop(&s1); current2 = pop(&s2); // If element of first tree is smaller, then // print it and push the right subtree. If the // element is larger, then we push it back to // the corresponding stack. if (current1->data < current2->data) { cout << current1->data << " " ; current1 = current1->right; push(&s2, current2); current2 = NULL; } else { cout << current2->data << " " ; current2 = current2->right; push(&s1, current1); current1 = NULL; } } } } /* Driver program to test above functions */ int main() { node *root1 = NULL, *root2 = NULL; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = newNode(3); root1->left = newNode(1); root1->right = newNode(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = newNode(4); root2->left = newNode(2); root2->right = newNode(6); // Print sorted nodes of both trees merge(root1, root2); return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> // Structure of a BST Node struct node { int data; struct node* left; struct node* right; }; //.................... START OF STACK RELATED //STUFF.................... // A stack node struct snode { struct node* t; struct snode* next; }; // Function to add an element k to stack void push( struct snode** s, struct node* k) { struct snode* tmp = ( struct snode*) malloc ( sizeof ( struct snode)); // perform memory check here tmp->t = k; tmp->next = *s; (*s) = tmp; } // Function to pop an element t from stack struct node* pop( struct snode** s) { struct node* t; struct snode* st; st = *s; (*s) = (*s)->next; t = st->t; free (st); return t; } // Function to check whether the stack is empty or not int isEmpty( struct snode* s) { if (s == NULL) return 1; return 0; } //.................... END OF STACK RELATED //STUFF.................... /* Utility function to create a new Binary Tree node */ struct node* newNode( int data) { struct node* temp = ( struct node*) malloc ( sizeof ( struct node)); temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } /* A utility function to print Inorder traversal of a Binary * Tree */ void inorder( struct node* root) { if (root != NULL) { inorder(root->left); printf ( "%d " , root->data); inorder(root->right); } } // The function to print data of two BSTs in sorted order void merge( struct node* root1, struct node* root2) { // s1 is stack to hold nodes of first BST struct snode* s1 = NULL; // Current node of first BST struct node* current1 = root1; // s2 is stack to hold nodes of second BST struct snode* s2 = NULL; // Current node of second BST struct node* current2 = root2; // If first BST is empty, then output is inorder // traversal of second BST if (root1 == NULL) { inorder(root2); return ; } // If second BST is empty, then output is inorder // traversal of first BST if (root2 == NULL) { inorder(root1); return ; } // Run the loop while there are nodes not yet printed. // The nodes may be in stack(explored, but not printed) // or may be not yet explored while (current1 != NULL || !isEmpty(s1) || current2 != NULL || !isEmpty(s2)) { // Following steps follow iterative Inorder // Traversal if (current1 != NULL || current2 != NULL) { // Reach the leftmost node of both BSTs and push // ancestors of leftmost nodes to stack s1 and // s2 respectively if (current1 != NULL) { push(&s1, current1); current1 = current1->left; } if (current2 != NULL) { push(&s2, current2); current2 = current2->left; } } else { // If we reach a NULL node and either of the // stacks is empty, then one tree is exhausted, // print the other tree if (isEmpty(s1)) { while (!isEmpty(s2)) { current2 = pop(&s2); current2->left = NULL; inorder(current2); } return ; } if (isEmpty(s2)) { while (!isEmpty(s1)) { current1 = pop(&s1); current1->left = NULL; inorder(current1); } return ; } // Pop an element from both stacks and compare // the popped elements current1 = pop(&s1); current2 = pop(&s2); // If element of first tree is smaller, then // print it and push the right subtree. If the // element is larger, then we push it back to // the corresponding stack. if (current1->data < current2->data) { printf ( "%d " , current1->data); current1 = current1->right; push(&s2, current2); current2 = NULL; } else { printf ( "%d " , current2->data); current2 = current2->right; push(&s1, current1); current1 = NULL; } } } } /* Driver program to test above functions */ int main() { struct node *root1 = NULL, *root2 = NULL; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = newNode(3); root1->left = newNode(1); root1->right = newNode(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = newNode(4); root2->left = newNode(2); root2->right = newNode(6); // Print sorted nodes of both trees merge(root1, root2); return 0; } |
Java
public class Merge2BST { /* A utility function to print Inorder traversal of a Binary Tree */ static void inorder(Node root) { if (root != null ) { inorder(root.left); System.out.print(root.data + " " ); inorder(root.right); } } // The function to print data of two BSTs in sorted // order static void merge(Node root1, Node root2) { // s1 is stack to hold nodes of first BST SNode s1 = new SNode(); // Current node of first BST Node current1 = root1; // s2 is stack to hold nodes of second BST SNode s2 = new SNode(); // Current node of second BST Node current2 = root2; // If first BST is empty, then output is inorder // traversal of second BST if (root1 == null ) { inorder(root2); return ; } // If second BST is empty, then output is inorder // traversal of first BST if (root2 == null ) { inorder(root1); return ; } // Run the loop while there are nodes not yet // printed. The nodes may be in stack(explored, but // not printed) or may be not yet explored while (current1 != null || !s1.isEmpty() || current2 != null || !s2.isEmpty()) { // Following steps follow iterative Inorder // Traversal if (current1 != null || current2 != null ) { // Reach the leftmost node of both BSTs and // push ancestors of leftmost nodes to stack // s1 and s2 respectively if (current1 != null ) { s1.push(current1); current1 = current1.left; } if (current2 != null ) { s2.push(current2); current2 = current2.left; } } else { // If we reach a NULL node and either of the // stacks is empty, then one tree is // exhausted, print the other tree if (s1.isEmpty()) { while (!s2.isEmpty()) { current2 = s2.pop(); current2.left = null ; inorder(current2); } return ; } if (s2.isEmpty()) { while (!s1.isEmpty()) { current1 = s1.pop(); current1.left = null ; inorder(current1); } return ; } // Pop an element from both stacks and // compare the popped elements current1 = s1.pop(); current2 = s2.pop(); // If element of first tree is smaller, then // print it and push the right subtree. If // the element is larger, then we push it // back to the corresponding stack. if (current1.data < current2.data) { System.out.print(current1.data + " " ); current1 = current1.right; s2.push(current2); current2 = null ; } else { System.out.print(current2.data + " " ); current2 = current2.right; s1.push(current1); current1 = null ; } } } System.out.println(s1.t); System.out.println(s2.t); } /* Driver code */ public static void main(String[] args) { Node root1 = null , root2 = null ; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = new Node( 3 ); root1.left = new Node( 1 ); root1.right = new Node( 5 ); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = new Node( 4 ); root2.left = new Node( 2 ); root2.right = new Node( 6 ); // Print sorted nodes of both trees merge(root1, root2); } } // Structure of a BST Node class Node { int data; Node left; Node right; public Node( int data) { // TODO Auto-generated constructor stub this .data = data; this .left = null ; this .right = null ; } } // A stack node class SNode { SNode head; Node t; SNode next; // Function to add an element k to stack void push(Node k) { SNode tmp = new SNode(); // Perform memory check here tmp.t = k; tmp.next = this .head; this .head = tmp; } // Function to pop an element t from stack Node pop() { SNode st; st = this .head; head = head.next; return st.t; } // Function to check whether the stack is empty or not boolean isEmpty() { if ( this .head == null ) return true ; return false ; } } // This code is contributed by nidhisebastian008 |
Python 3
# Class to create a new Tree Node class newNode: def __init__( self , data: int ): self .data = data self .left = None self .right = None def inorder(root: newNode): if root: inorder(root.left) print (root.data, end = " " ) inorder(root.right) def merge(root1: newNode, root2: newNode): # s1 is stack to hold nodes of first BST s1 = [] # Current node of first BST current1 = root1 # s2 is stack to hold nodes of first BST s2 = [] # Current node of second BST current2 = root2 # If first BST is empty then the output is the # inorder traversal of the second BST if not root1: return inorder(root2) # If the second BST is empty then the output is the # inorder traversal of the first BST if not root2: return inorder(root1) # Run the loop while there are nodes not yet printed. # The nodes may be in stack(explored, but not printed) # or may be not yet explored while current1 or s1 or current2 or s2: # Following steps follow iterative Inorder Traversal if current1 or current2: # Reach the leftmost node of both BSTs and push ancestors of # leftmost nodes to stack s1 and s2 respectively if current1: s1.append(current1) current1 = current1.left if current2: s2.append(current2) current2 = current2.left else : # If we reach a NULL node and either of the stacks is empty, # then one tree is exhausted, print the other tree if not s1: while s2: current2 = s2.pop() current2.left = None inorder(current2) return if not s2: while s1: current1 = s1.pop() current1.left = None inorder(current1) return # Pop an element from both stacks and compare the # popped elements current1 = s1.pop() current2 = s2.pop() # If element of first tree is smaller, then print it # and push the right subtree. If the element is larger, # then we push it back to the corresponding stack. if current1.data < current2.data: print (current1.data, end = " " ) current1 = current1.right s2.append(current2) current2 = None else : print (current2.data, end = " " ) current2 = current2.right s1.append(current1) current1 = None # Driver code def main(): # Let us create the following tree as first tree # 3 # / \ # 1 5 root1 = newNode( 3 ) root1.left = newNode( 1 ) root1.right = newNode( 5 ) # Let us create the following tree as second tree # 4 # / \ # 2 6 # root2 = newNode( 4 ) root2.left = newNode( 2 ) root2.right = newNode( 6 ) merge(root1, root2) if __name__ = = "__main__" : main() # This code is contributed by Koushik Reddy Bukkasamudram |
C#
// C# program to implement the // above approach using System; class Merge2BST { /* A utility function to print Inorder traversal of a Binary Tree */ static void inorder(Node root) { if (root != null ) { inorder(root.left); Console.Write(root.data + " " ); inorder(root.right); } } // The function to print data // of two BSTs in sorted order static void merge(Node root1, Node root2) { // s1 is stack to hold nodes // of first BST SNode s1 = new SNode(); // Current node of first BST Node current1 = root1; // s2 is stack to hold nodes // of second BST SNode s2 = new SNode(); // Current node of second BST Node current2 = root2; // If first BST is empty, then // output is inorder traversal // of second BST if (root1 == null ) { inorder(root2); return ; } // If second BST is empty, // then output is inorder // traversal of first BST if (root2 == null ) { inorder(root1); return ; } // Run the loop while there // are nodes not yet printed. // The nodes may be in stack // (explored, but not printed) // or may be not yet explored while (current1 != null || !s1.isEmpty() || current2 != null || !s2.isEmpty()) { // Following steps follow // iterative Inorder Traversal if (current1 != null || current2 != null ) { // Reach the leftmost node of // both BSTs and push ancestors // of leftmost nodes to stack // s1 and s2 respectively if (current1 != null ) { s1.push(current1); current1 = current1.left; } if (current2 != null ) { s2.push(current2); current2 = current2.left; } } else { // If we reach a NULL node and // either of the stacks is empty, // then one tree is exhausted, // print the other tree if (s1.isEmpty()) { while (!s2.isEmpty()) { current2 = s2.pop(); current2.left = null ; inorder(current2); } return ; } if (s2.isEmpty()) { while (!s1.isEmpty()) { current1 = s1.pop(); current1.left = null ; inorder(current1); } return ; } // Pop an element from both // stacks and compare the // popped elements current1 = s1.pop(); current2 = s2.pop(); // If element of first tree is // smaller, then print it // and push the right subtree. // If the element is larger, // then we push it back to the // corresponding stack. if (current1.data < current2.data) { Console.Write(current1.data + " " ); current1 = current1.right; s2.push(current2); current2 = null ; } else { Console.Write(current2.data + " " ); current2 = current2.right; s1.push(current1); current1 = null ; } } } Console.Write(s1.t + "\n" ); Console.Write(s2.t + "\n" ); } // Driver code public static void Main( string [] args) { Node root1 = null , root2 = null ; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = new Node(3); root1.left = new Node(1); root1.right = new Node(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = new Node(4); root2.left = new Node(2); root2.right = new Node(6); // Print sorted nodes of // both trees merge(root1, root2); } } // Structure of a BST Node class Node { public int data; public Node left; public Node right; public Node( int data) { // TODO Auto-generated // constructor stub this .data = data; this .left = null ; this .right = null ; } } // A stack node class SNode { SNode head; public Node t; SNode next; // Function to add an element // k to stack public void push(Node k) { SNode tmp = new SNode(); // Perform memory check here tmp.t = k; tmp.next = this .head; this .head = tmp; } // Function to pop an element // t from stack public Node pop() { SNode st; st = this .head; head = head.next; return st.t; } // Function to check whether // the stack is empty or not public bool isEmpty() { if ( this .head == null ) return true ; return false ; } } // This code is contributed by Rutvik_56 |
Javascript
<script> // JavaScript program to implement the // above approach // Structure of a BST Node class Node { constructor(data) { // TODO Auto-generated // constructor stub this .data = data; this .left = null ; this .right = null ; } } // A stack node class SNode { constructor() { this .head = null ; this .t = null ; this .next = null ; } // Function to add an element // k to stack push(k) { var tmp = new SNode(); // Perform memory check here tmp.t = k; tmp.next = this .head; this .head = tmp; } // Function to pop an element // t from stack pop() { var st; st = this .head; this .head = this .head.next; return st.t; } // Function to check whether // the stack is empty or not isEmpty() { if ( this .head == null ) return true ; return false ; } } /* A utility function to print Inorder traversal of a Binary Tree */ function inorder(root) { if (root != null ) { inorder(root.left); document.write(root.data + " " ); inorder(root.right); } } // The function to print data // of two BSTs in sorted order function merge(root1, root2) { // s1 is stack to hold nodes // of first BST var s1 = new SNode(); // Current node of first BST var current1 = root1; // s2 is stack to hold nodes // of second BST var s2 = new SNode(); // Current node of second BST var current2 = root2; // If first BST is empty, then // output is inorder traversal // of second BST if (root1 == null ) { inorder(root2); return ; } // If second BST is empty, // then output is inorder // traversal of first BST if (root2 == null ) { inorder(root1); return ; } // Run the loop while there // are nodes not yet printed. // The nodes may be in stack // (explored, but not printed) // or may be not yet explored while ( current1 != null || !s1.isEmpty() || current2 != null || !s2.isEmpty() ) { // Following steps follow // iterative Inorder Traversal if (current1 != null || current2 != null ) { // Reach the leftmost node of // both BSTs and push ancestors // of leftmost nodes to stack // s1 and s2 respectively if (current1 != null ) { s1.push(current1); current1 = current1.left; } if (current2 != null ) { s2.push(current2); current2 = current2.left; } } else { // If we reach a NULL node and // either of the stacks is empty, // then one tree is exhausted, // print the other tree if (s1.isEmpty()) { while (!s2.isEmpty()) { current2 = s2.pop(); current2.left = null ; inorder(current2); } return ; } if (s2.isEmpty()) { while (!s1.isEmpty()) { current1 = s1.pop(); current1.left = null ; inorder(current1); } return ; } // Pop an element from both // stacks and compare the // popped elements current1 = s1.pop(); current2 = s2.pop(); // If element of first tree is // smaller, then print it // and push the right subtree. // If the element is larger, // then we push it back to the // corresponding stack. if (current1.data < current2.data) { document.write(current1.data + " " ); current1 = current1.right; s2.push(current2); current2 = null ; } else { document.write(current2.data + " " ); current2 = current2.right; s1.push(current1); current1 = null ; } } } document.write(s1.t + "<br>" ); document.write(s2.t + "<br>" ); } // Driver code var root1 = null , root2 = null ; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = new Node(3); root1.left = new Node(1); root1.right = new Node(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = new Node(4); root2.left = new Node(2); root2.right = new Node(6); // Print sorted nodes of // both trees merge(root1, root2); </script> |
1 2 3 4 5 6
Time Complexity: O(M+N), M is the size of the first tree and N is the size of the second tree
Auxiliary Space: O(H1 + H2), H1 is the height of the first tree and H2 is the height of the second tree
Merge two BSTs using Inbuilt Stack Data structure:
In this method, we use the inbuilt stack that is present in the STL library so as to get rid of the implementation of the stack part of the code that has been done in the previous implementation.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> using namespace std; // Structure of a BST Node class Node { public : int val; Node* left; Node* right; }; /* Utility function to create a new Binary Tree Node */ Node* newNode( int data) { Node* temp = new Node; temp->val = data; temp->left = nullptr; temp->right = nullptr; return temp; } vector< int > mergeTwoBST(Node* root1, Node* root2) { vector< int > res; stack<Node*> s1, s2; while (root1 || root2 || !s1.empty() || !s2.empty()) { while (root1) { s1.push(root1); root1 = root1->left; } while (root2) { s2.push(root2); root2 = root2->left; } // Step 3 Case 1:- if (s2.empty() || (!s1.empty() && s1.top()->val <= s2.top()->val)) { root1 = s1.top(); s1.pop(); res.push_back(root1->val); root1 = root1->right; } // Step 3 case 2 :- else { root2 = s2.top(); s2.pop(); res.push_back(root2->val); root2 = root2->right; } } return res; } /* Driver program to test above functions */ int main() { Node *root1 = nullptr, *root2 = nullptr; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = newNode(3); root1->left = newNode(1); root1->right = newNode(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = newNode(4); root2->left = newNode(2); root2->right = newNode(6); // Print sorted Nodes of both trees vector< int > ans = mergeTwoBST(root1, root2); for ( auto it : ans) cout << it << " " ; return 0; } // This code is contributed by Aditya kumar (adityakumar129) |
Java
// Java Code for the above approach import java.io.*; import java.util.*; class GFG { static void mergeTwoBST(Node root1, Node root2) { List<Integer> res = new ArrayList<Integer>(); Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); while (root1 != null || root2 != null || !s1.isEmpty() || !s2.isEmpty()) { while (root1 != null ) { s1.push(root1); root1 = root1.left; } while (root2 != null ) { s2.push(root2); root2 = root2.left; } if (s2.isEmpty() || (!s1.isEmpty() && s1.peek().data <= s2.peek().data)) { root1 = s1.peek(); s1.pop(); res.add(root1.data); root1 = root1.right; } else { root2 = s2.peek(); s2.pop(); res.add(root2.data); root2 = root2.right; } } for ( int i = 0 ; i < res.size(); i++) { System.out.print(res.get(i) + " " ); } } public static void main(String[] args) { Node root1 = null , root2 = null ; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = new Node( 3 ); root1.left = new Node( 1 ); root1.right = new Node( 5 ); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = new Node( 4 ); root2.left = new Node( 2 ); root2.right = new Node( 6 ); mergeTwoBST(root1, root2); } } // Structure of a BST Node class Node { int data; Node left; Node right; public Node( int data) { // TODO Auto-generated constructor stub this .data = data; this .left = null ; this .right = null ; } } // This code is contributed by lokesh(lokeshmvs21). |
Python3
# Python program to Merge two BSTs with limited extra space # Structure of a BST Node class Node: def __init__( self , val): self .val = val self .left = None self .right = None def mergeTwoBST(root1, root2): res = [] s1, s2 = [], [] while root1 or root2 or s1 or s2: while root1: s1.append(root1) root1 = root1.left while root2: s2.append(root2) root2 = root2.left # Step 3 Case 1:- if not s2 or (s1 and s1[ - 1 ].val < = s2[ - 1 ].val): root1 = s1[ - 1 ] del s1[ - 1 ] res.append(root1.val) root1 = root1.right # Step 3 case 2 :- else : root2 = s2[ - 1 ] del s2[ - 1 ] res.append(root2.val) root2 = root2.right return res # Driver program to test above functions if __name__ = = '__main__' : root1 = None root2 = None ''' Let us create the following tree as first tree 3 / \ 1 5 ''' root1 = Node( 3 ) root1.left = Node( 1 ) root1.right = Node( 5 ) ''' Let us create the following tree as second tree 4 / \ 2 6 ''' root2 = Node( 4 ) root2.left = Node( 2 ) root2.right = Node( 6 ) ans = mergeTwoBST(root1, root2) for x in ans: print (x, end = " " ) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# Code for the above approach using System; using System.Collections.Generic; // Structure of a BST Node class Node { public int data; public Node left; public Node right; public Node( int data) { this .data = data; this .left = null ; this .right = null ; } } class GFG { static void mergeTwoBST(Node root1, Node root2) { List< int > res = new List< int >(); Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); while (root1 != null || root2 != null || s1.Count != 0 || s2.Count != 0) { while (root1 != null ) { s1.Push(root1); root1 = root1.left; } while (root2 != null ) { s2.Push(root2); root2 = root2.left; } if (s2.Count == 0 || (s1.Count != 0 && s1.Peek().data <= s2.Peek().data)) { root1 = s1.Peek(); s1.Pop(); res.Add(root1.data); root1 = root1.right; } else { root2 = s2.Peek(); s2.Pop(); res.Add(root2.data); root2 = root2.right; } } for ( int i = 0; i < res.Count; i++) { Console.Write(res[i] + " " ); } } public static void Main(String[] args) { Node root1 = null , root2 = null ; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = new Node(3); root1.left = new Node(1); root1.right = new Node(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = new Node(4); root2.left = new Node(2); root2.right = new Node(6); mergeTwoBST(root1, root2); } } // This code is contributed by Tapesh (tapeshdua420) |
Javascript
// JavaScript Code for the above approach function Node(data, left = null , right = null ) { this .data = data; this .left = left; this .right = right; } function mergeTwoBST(root1, root2) { let res = []; let s1 = []; let s2 = []; while (root1 !== null || root2 !== null || s1.length !== 0 || s2.length !== 0) { while (root1 !== null ) { s1.push(root1); root1 = root1.left; } while (root2 !== null ) { s2.push(root2); root2 = root2.left; } if (s2.length === 0 || (s1.length !== 0 && s1[s1.length - 1].data <= s2[s2.length - 1].data)) { root1 = s1.pop(); res.push(root1.data); root1 = root1.right; } else { root2 = s2.pop(); res.push(root2.data); root2 = root2.right; } } console.log(res.join( ' ' )); } function main() { let root1 = null ; let root2 = null ; /* Create the following tree as first tree 3 / \ 1 5 */ root1 = new Node(3, new Node(1), new Node(5)); /* Create the following tree as second tree 4 / \ 2 6 */ root2 = new Node(4, new Node(2), new Node(6)); mergeTwoBST(root1, root2); } main(); // This code is contributed by lokesh. |
1 2 3 4 5 6
Time Complexity: O(M+N), M is the size of the first tree and N is the size of the second tree
Auxiliary Space: O(H1 + H2), H1 is the height of the first tree and H2 is the height of the second tree
Merge two BSTs using Doubly Linked List
Follow the steps below to solve the problem:
- Convert BST into sorted Doubly Linked List(Flatten a binary tree into linked list)
Time Complexity: O(N),N is the size of the tree
Auxiliary Space: O(H),H is the height of the tree
- Merge 2 sorted Doubly Linked List(Merge two sorted linked lists)
Time Complexity: O(M+N), M is the size of the first tree and N is the size of the second tree
Auxiliary Space: O(1)
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; class Node { public : int val; Node* left; Node* right; }; /* Utility function to create a new Binary Tree Node */ Node* newNode( int data) { Node* temp = new Node; temp->val = data; temp->left = nullptr; temp->right = nullptr; return temp; } /* UTILITY FUNCTIONS */ /* MoveNode() function takes the node from the front of the source, and move it to the front of the dest. It is an error to call this with the source list empty. Before calling MoveNode(): source == {1, 2, 3} dest == {1, 2, 3} After calling MoveNode(): source == {2, 3} dest == {1, 1, 2, 3} */ void MoveNode(Node** destRef, Node** sourceRef) { /* the front source node */ Node* newNode = *sourceRef; assert (newNode != NULL); /* Advance the source pointer */ *sourceRef = newNode->right; /* Link the old dest of the new node */ newNode->right = *destRef; /* Move dest to point to the new node */ *destRef = newNode; } /* Merge sorted Double linked list */ Node* mergeLinkedList(Node* a, Node* b) { Node dummy; /* tail points to the last result node */ Node* tail = &dummy; /* so tail->next is the place to add new nodes to the result. */ dummy.right = NULL; while (1) { if (a == NULL) { /* if either list runs out, use the other list */ tail->right = b; break ; } else if (b == NULL) { tail->right = a; break ; } if (a->val <= b->val) MoveNode(&(tail->right), &a); else MoveNode(&(tail->right), &b); tail = tail->right; } return (dummy.right); } /* convert sorted Double linked list */ void convertIntoSortedDLL(Node* root, Node*& head) { //base case if (root == NULL) return ; convertIntoSortedDLL(root->right, head); root->right = head; if (head != NULL) head->left = root; head = root; convertIntoSortedDLL(root->left, head); } /* Function to print nodes in a given linked list */ void printList(Node* head) { while (head) { printf ( "%d " , head->val); head = head->right; } } int main() { Node *root1 = nullptr, *root2 = nullptr; /* Let us create the following tree as first tree 3 / \ 1 5 */ root1 = newNode(3); root1->left = newNode(1); root1->right = newNode(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ root2 = newNode(4); root2->left = newNode(2); root2->right = newNode(6); // Convert BST into sorted DLL Node*head1=NULL; Node*head2=NULL; convertIntoSortedDLL(root1,head1); convertIntoSortedDLL(root2,head2); // merge sorted DLL Node* ans = mergeLinkedList(head1, head2); printList(ans); return 0; // This code is contributed by Ajay Rawat(theajayrawat) } |
Java
// Java code addition import java.io.*; import java.util.*; class Node { int data; Node left, right; /* Utility function to create a new Binary Tree Node */ public Node( int data) { this .data = data; this .left = null ; this .right = null ; } } class BinaryTree { Node root; public void insert( int data) { root = insertRec(root, data); } public Node insertRec(Node root, int data) { if (root == null ) { root = new Node(data); return root; } if (data < root.data) { root.left = insertRec(root.left, data); } else if (data > root.data) { root.right = insertRec(root.right, data); } return root; } /* convert sorted Double linked list */ public void convertIntoSortedDLL(Node root, Node[] head) { if (root == null ) { return ; } convertIntoSortedDLL(root.right, head); root.right = head[ 0 ]; if (head[ 0 ] != null ) { head[ 0 ].left = root; } head[ 0 ] = root; convertIntoSortedDLL(root.left, head); } /* Merge sorted Double linked list */ public Node mergeLinkedList(Node head1, Node head2) { Node dummy = new Node( 0 ); /* tail points to the last result node */ Node tail = dummy; /* so tail->next is the place to add new nodes to the result. */ while ( true ) { if (head1 == null ) { /* if either list runs out, use the other list */ tail.right = head2; break ; } if (head2 == null ) { tail.right = head1; break ; } if (head1.data <= head2.data) { tail.right = head1; head1.left = tail; head1 = head1.right; } else { tail.right = head2; head2.left = tail; head2 = head2.right; } tail = tail.right; } Node res = dummy.right; res.left = null ; return res; } /* Function to print nodes in a given linked list */ public void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.right; } } } public class Main { public static void main(String[] args) { BinaryTree tree1 = new BinaryTree(); BinaryTree tree2 = new BinaryTree(); /* Let us create the following tree as first tree 3 / \ 1 5 */ tree1.insert( 3 ); tree1.insert( 1 ); tree1.insert( 5 ); /* Let us create the following tree as second tree 4 / \ 2 6 */ tree2.insert( 4 ); tree2.insert( 2 ); tree2.insert( 6 ); // Convert BST into sorted DLL Node[] head1 = { null }; Node[] head2 = { null }; tree1.convertIntoSortedDLL(tree1.root, head1); tree2.convertIntoSortedDLL(tree2.root, head2); // merge sorted DLL Node ans = tree1.mergeLinkedList(head1[ 0 ], head2[ 0 ]); tree1.printList(ans); } } // The code is contributed by Arushi Goel. |
Python3
class Node: def __init__( self , data): # Utility function to create a new Binary Tree Node self .data = data self .left = None self .right = None class BinaryTree: def __init__( self ): self .root = None def insert( self , data): self .root = self .insertRec( self .root, data) def insertRec( self , root, data): if root is None : root = Node(data) return root if data < root.data: root.left = self .insertRec(root.left, data) elif data > root.data: root.right = self .insertRec(root.right, data) return root # convert sorted Double linked list def convertIntoSortedDLL( self , root, head): # base case if root is None : return self .convertIntoSortedDLL(root.right, head) root.right = head[ 0 ] if head[ 0 ] is not None : head[ 0 ].left = root head[ 0 ] = root self .convertIntoSortedDLL(root.left, head) # Merge sorted Double linked list def mergeLinkedList( self , head1, head2): dummy = Node( 0 ) # tail points to the last result node tail = dummy # so tail->next is the place to # add new nodes to the result. while True : if head1 is None : # if either list runs out, use the # other list tail.right = head2 break if head2 is None : tail.right = head1 break if head1.data < = head2.data: tail.right = head1 head1.left = tail head1 = head1.right else : tail.right = head2 head2.left = tail head2 = head2.right tail = tail.right res = dummy.right res.left = None return res # Function to print nodes in a given linked list def printList( self , node): while node is not None : print (node.data, end = " " ) node = node.right if __name__ = = "__main__" : tree1 = BinaryTree() tree2 = BinaryTree() # Let us create the following tree as first tree # 3 # / \ # 1 5 tree1.insert( 3 ) tree1.insert( 1 ) tree1.insert( 5 ) # Let us create the following tree as second tree # 4 # / \ # 2 6 tree2.insert( 4 ) tree2.insert( 2 ) tree2.insert( 6 ) # Convert BST into sorted DLL head1 = [ None ] head2 = [ None ] tree1.convertIntoSortedDLL(tree1.root, head1) tree2.convertIntoSortedDLL(tree2.root, head2) # merge sorted DLL ans = tree1.mergeLinkedList(head1[ 0 ], head2[ 0 ]) tree1.printList(ans) |
C#
using System; public class Node { public int data; public Node left; public Node right; /* Utility function to create a new Binary Tree Node */ public Node( int data) { this .data = data; this .left = null ; this .right = null ; } } public class BinaryTree { public Node root; public BinaryTree() { this .root = null ; } public void insert( int data) { this .root = insertRec( this .root, data); } private Node insertRec(Node root, int data) { if (root == null ) { root = new Node(data); return root; } if (data < root.data) { root.left = insertRec(root.left, data); } else if (data > root.data) { root.right = insertRec(root.right, data); } return root; } /* convert sorted Double linked list */ public void convertIntoSortedDLL(Node root, ref Node head) { // base case if (root == null ) { return ; } convertIntoSortedDLL(root.right, ref head); root.right = head; if (head != null ) { head.left = root; } head = root; convertIntoSortedDLL(root.left, ref head); } /* Merge sorted Double linked list */ public Node mergeLinkedList(Node head1, Node head2) { Node dummy = new Node(0); /* tail points to the last result node */ Node tail = dummy; /* so tail->next is the place to add new nodes to the result. */ while ( true ) { if (head1 == null ) { /* if either list runs out, use the other list */ tail.right = head2; break ; } if (head2 == null ) { tail.right = head1; break ; } if (head1.data <= head2.data) { tail.right = head1; head1.left = tail; head1 = head1.right; } else { tail.right = head2; head2.left = tail; head2 = head2.right; } tail = tail.right; } Node res = dummy.right; res.left = null ; return res; } /* Function to print nodes in a given linked list */ public void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.right; } } } public class Program { public static void Main() { BinaryTree tree1 = new BinaryTree(); BinaryTree tree2 = new BinaryTree(); /* Let us create the following tree as first tree 3 / \ 1 5 */ tree1.insert(3); tree1.insert(1); tree1.insert(5); /* Let us create the following tree as second tree 4 / \ 2 6 */ tree2.insert(4); tree2.insert(2); tree2.insert(6); // Convert BST into sorted DLL Node head1 = null ; Node head2 = null ; tree1.convertIntoSortedDLL(tree1.root, ref head1); tree2.convertIntoSortedDLL(tree2.root, ref head2); // merge sorted DLL Node ans = tree1.mergeLinkedList(head1, head2); tree1.printList(ans); } } |
Javascript
// javascript code addition class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } class BinaryTree { constructor() { this .root = null ; } insert(data) { this .root = this .insertRec( this .root, data); } insertRec(root, data) { if (root === null ) { root = new Node(data); return root; } if (data < root.data) { root.left = this .insertRec(root.left, data); } else if (data > root.data) { root.right = this .insertRec(root.right, data); } return root; } convertIntoSortedDLL(root, head) { if (root === null ) { return ; } this .convertIntoSortedDLL(root.right, head); root.right = head[0]; if (head[0] !== null ) { head[0].left = root; } head[0] = root; this .convertIntoSortedDLL(root.left, head); } mergeLinkedList(head1, head2) { const dummy = new Node(0); let tail = dummy; while ( true ) { if (head1 === null ) { tail.right = head2; break ; } if (head2 === null ) { tail.right = head1; break ; } if (head1.data <= head2.data) { tail.right = head1; head1.left = tail; head1 = head1.right; } else { tail.right = head2; head2.left = tail; head2 = head2.right; } tail = tail.right; } const res = dummy.right; res.left = null ; return res; } printList(node) { while (node !== null ) { process.stdout.write(node.data+ " " ); node = node.right; } } } const tree1 = new BinaryTree(); const tree2 = new BinaryTree(); tree1.insert(3); tree1.insert(1); tree1.insert(5); tree2.insert(4); tree2.insert(2); tree2.insert(6); const head1 = [ null ]; const head2 = [ null ]; tree1.convertIntoSortedDLL(tree1.root, head1); tree2.convertIntoSortedDLL(tree2.root, head2); const ans = tree1.mergeLinkedList(head1[0], head2[0]); tree1.printList(ans); // The code is contributed by Nidhi goel. |
1 2 3 4 5 6
Time Complexity: O(M+N), M is the size of the first tree and N is the size of the second tree
Auxiliary Space: O(max(H1,H2)), H1 is the height of the first tree and H2 is the height of the second tree
Contact Us