Python JavaScript HTML CSS C Java C# / .NET C++ TypeScript Dart

Merge Two Balanced Binary Search Trees

Tree sizes are typically provided as input in the solutions below. In cases where the size is not explicitly mentioned, it can be calculated by navigating through the tree structure.

Method 1 (Insert first tree elements into second tree):

Add each element from the initial Binary Search Tree (BST) individually into the second BST. The process of inserting an element into a self-balancing BST is efficient, taking logarithmic time complexity. This means that for a BST of size n, the time taken is O(log n). When transferring elements, the time complexity of this operation is the sum of logarithms from Log(n) to Log(m+n-1), resulting in a time complexity range of mlog(n) to mlog(m+n-1). To optimize this process, it is advisable to choose the smaller tree as the first BST.

Method 2 (Merge Inorder Traversals):

  • ✅ Perform an inorder traversal of the first tree and save the results in one temp array arr1. This process requires O(m) time.
  • ✅ Perform an inorder traversal of the second tree and save the results in another temporary array arr2. This procedure takes O(n) time.
  • ✅ The arrays that were formed in steps 1 and 2 are sorted arrays. Merge the two sorted arrays into a single m + n array. This procedure takes O(m+n) time.
  • ✅ Using the technique described in this post, create a balanced tree from the merged array. This procedure takes O(m+n) time.

This approach has a time complexity of O(m+n), which outperforms method 1. Even in scenarios where the input Binary Search Trees are unbalanced, this procedure still operates in O(m+n) time.

This method's implementation is shown below.

C++ Program:

Example

// Here we are merging two balanced binary search trees in a C++ program
#include<bits/stdc++.h>
using namespace std ;

class node
{
	public:
	int val ;
	node* left_node ;
	node* right_node ;
} ;
int *merger ( int array1 [ ] , int array2 [ ] , int x , int y ) ;
void storing_Inorder(node* nodes, int inOrder1[],
							int *index_pointer ) ;

node* sortedArrToBST ( int arr [ ] , int first , int last ) ;

node* mergerTrees ( node *rt1 , node *rt2 , int x , int y )
{
	
	int *array1 = new int[x];
	int index = 0;
	storing_Inorder(rt1, array1, &index);

	
	int *array2 = new int[y];
	int j = 0;
	storing_Inorder(rt2, array2, &j);

	
	int *mergedArr = merger(array1, array2, x, y);

	
	return sortedArrToBST (mergedArr, 0, x + y - 1);
}

node* newNode(int val)
{
	node* Node = new node();
	Node->val = val;
	Node->left_node = NULL;
	Node->right_node = NULL;

	return(Node);
}

void printInorder(node* node)
{
	if (node == NULL)
		return;

	
	printInorder(node->left_node);

	cout << node->val << " ";

	printInorder(node->right_node);
}

int *merger(int array1[], int array2[], int x, int y)
{
	int *mergedArr = new int[x + y];
	int index = 0, j = 0, k = 0;
	while (index < x && j < y)
	{
		
		if (array1[index] < array2[j])
		{
			mergedArr[k] = array1[index];
			index++;
		}
		else
		{
			mergedArr[k] = array2[j];
			j++;
		}
		k++;
	}

	
	while (index < x)
	{
		mergedArr[k] = array1[index];
		index++; k++;
	}

	
	while (j < y)
	{
		mergedArr[k] = array2[j];
		j++; k++;
	}

	return mergedArr;
}

void storing_Inorder(node* node, int inorder[], int *index_ptr)
{
	if (node == NULL)
		return;

	
	storing_Inorder(node->left_node, inorder, index_ptr);

	inorder[*index_ptr] = node->val;
	(*index_ptr)++; 

	
	storing_Inorder(node->right_node, inorder, index_ptr);
}

node* sortedArrToBST(int arr[], int first, int last)
{
	/* Base Case */
	if (first > last)
	return NULL;

	int mid = (first + last)/2;
	node *root = newNode(arr[mid]);

	
	root->left_node = sortedArrToBST(arr, first, mid-1);
	root->right_node = sortedArrToBST(arr, mid+1, last);

	return root;
}

/* Driver code*/
int main()
{
	/* Create following tree as first balanced BST
		110
		/ \
		60 400
	/ \
	10 90
	*/
	node *rt1 = newNode(100);
	rt1->left_node	 = newNode(60);
	rt1->right_node = newNode(400);
	rt1->left_node->left_node = newNode(10);
	rt1->left_node->right_node = newNode(90);

	
	node *rt2 = newNode(110);
	rt2->left_node	 = newNode(30);
	rt2->right_node = newNode(130);

	node *mergedTree = mergerTrees(rt1, rt2, 5, 3);

	cout << "Following is Inorder traversal of the merged tree \n";
	printInorder(mergedTree);

	return 0;
}

Output:

Output

Following is Inorder traversal of the merged tree 
10 30 60 90 100 110 130 400

C Program:

Example

// Merging two balanced binary search trees in C
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has the following attributes: val, 
left node child pointer, and right node child pointer. */
struct node
{
	int val;
	struct node* left_node;
	struct node* right_node;
};

// a practical method for combining two sorted arrays into one
int *merger(int array1[], int array2[], int x, int y);

// an utility method that keeps the results of an inorder1 tree traversal in an inorder1 array
void storing_Inorder(struct node* nodes, int inorder1[], int *index_pointer);

// a method that builds a balanced binary search tree from an array that has been sorted
struct node* sortedArrToBST(int array[], int first, int last);

/* Two balanced BSTs with rt1 and rt2 as their roots are combined using this function.
The sizes of the trees are x and y, respectively */
struct node* mergedTrees(struct node *rt1, struct node *rt2, int x, int y)
{
	// Keep the first tree's inorder1 traverse in an array array1[]
	int *array1 = new int[x];
	int index = 0;
	storing_Inorder(rt1, array1, &index);

	// Keep the second tree's inorder1 traverse in another array array2[]
	int *array2 = new int[y];
	int j = 0;
	storing_Inorder(rt2, array2, &j);

	// Add the two sorted arrays together.
	int *mergedArr = merger(array1, array2, x, y);

	// Create a tree from the combined array and return the tree's root.
	return sortedArrToBST (mergedArr, 0, x+y-1);
}

/* Allocating a new node with the specified val and NULL left node 
and right node pointers is done using a helper function. */
struct node* newNode(int val)
{
	struct node* nodes = (struct node*)
						malloc(sizeof(struct node));
	nodes->val = val;
	nodes->left_node = NULL;
	nodes->right_node = NULL;

	return(nodes);
}

// a useful function that prints the inorder1 traversal of a binary tree given to it
void printInorder(struct node* nodes)
{
	if (nodes == NULL)
		return;

	/* first recur on the child of left node */
	printInorder(nodes->left_node);

	printf("%d ", nodes->val);

	/* now repeat on child of right node */
	printInorder(nodes->right_node);
}

// a practical method for combining two sorted arrays into one
int *merger(int array1[], int array2[], int x, int y)
{
	// mergedArr[] will include the outcome.
	int *mergedArr = new int[x + y];
	int index = 0, j = 0, k = 0;

	// traverse each of the two arrays
	while (index < x && j < y)
	{
		// A smaller element should be chosen and placed in mergedArr.
		if (array1[index] < array2[j])
		{
			mergedArr[k] = array1[index];
			index++;
		}
		else
		{
			mergedArr[k] = array2[j];
			j++;
		}
		k++;
	}

	// if the first array contains more elements
	while (index < x)
	{
		mergedArr[k] = array1[index];
		index++; k++;
	}

	// if the second array contains more elements
	while (j < y)
	{
		mergedArr[k] = array2[j];
		j++; k++;
	}

	return mergedArr;
}

// An aid that saves the inorder1 traverse of a tree anchored at a node
void storing_Inorder(struct node* nodes, int inorder1[], int *index_pointer)
{
	if (nodes == NULL)
		return;

	/* first recur on the child of left node*/
	storing_Inorder(nodes->left_node, inorder1, index_pointer);

	inorder1[*index_pointer] = nodes->val;
	(*index_pointer)++; // raise the index for the next entry

	//now repeat on child of right node
	storing_Inorder(nodes->right_node, inorder1, index_pointer);
}

// A method that builds a balanced binary search tree from an array that has been sorted
struct node* sortedArrToBST(int array[], int first, int last)
{
	/* Base Case */
	if (first > last)
	return NULL;

	/* Make the centre element the root by taking it. */
	int mid = (first + last)/2;
	struct node *root = newNode(array[mid]);

	/* Create the left node subtree iteratively and make it 
    a left node child of the root. */
	root->left_node = sortedArrToBST(array, first, mid-1);

	/* Create the right node subtree iteratively and make it 
    a right node child of the root. */
	root->right_node = sortedArrToBST(array, mid+1, last);

	return root;
}

/* Driver program to test above functions*/
int main()
{
	/* The following tree should be the first balanced BST.
		110
		/ \
		60 400
	/ \
	10 90
	*/
	struct node *rt1 = newNode(110);
	rt1->left_node		 = newNode(60);
	rt1->right_node	 = newNode(400);
	rt1->left_node->left_node = newNode(10);
	rt1->left_node->right_node = newNode(90);

	/* The following tree should be the second balanced BST.
			100
		/ \
		30 130
	*/
	struct node *rt2 = newNode(100);
	rt2->left_node		 = newNode(30);
	rt2->right_node	 = newNode(130);

	struct node *mergedTree = mergedTrees(rt1, rt2, 5, 3);

	printf ("Following is inorder1 traversal of the merged tree \n");
	printInorder(mergedTree);

	getchar();
	return 0;
}

Output:

Output

Following is inorder1 traversal of the merged tree 
10 30 60 90 100 110 130 400

Method 3 (DLL-Based In-Place Merge):

  • ✅ To merge trees in place, we can utilize a Doubly Linked List. The steps are as follows.
  • ✅ In place, convert the two Binary Search Trees into a doubly linked list (Refer to this post for this step).
  • ✅ Combine two sorted Linked Lists.
  • ✅ Generate a Balanced Binary Search Tree using the merged list from step 2. (For more information on this step)

This function's time complexity remains O(m+n) as it carries out the conversion directly within the existing memory space.

C++ Program:

Example

// C++ Code for the above approach

#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has the following 
attributes: val, left node child pointer,
and right node child pointer.*/
class Node {
public:
	int val;
	Node* left_node;
	Node* right_node;
};

// a method that produces a new Node
Node* newNode(int val)
{
	Node* nodes = new Node();
	nodes->val = val;
	nodes->left_node = NULL;
	nodes->right_node = NULL;

	return (nodes);
}

// Function to create a doubly 
// linked list from bst
void bstreeTodllist(Node* rt, Node*& hd)
{
	// if rt is NULL
	if (!rt)
		return;

	// Recursively convert the right node subtree
	bstreeTodllist(rt->right_node, hd);

	// Update rt
	rt->right_node = hd;

	// if hd is not NULL
	if (hd) {

		// Update left_node of the hd
		hd->left_node = rt;
	}

	// Update hd
	hd = rt;

	// Recursively convert the left node subtree
	bstreeTodllist(rt->left_node, hd);
}

// combining two sorted linked lists function
Node* mergedLinkedList(Node* hd1, Node* hd2)
{

	//Create the result list's hd and tl
	Node* hd = NULL;
	Node* tl = NULL;

	while (hd1 && hd2) {

		if (hd1->val < hd2->val) {

			if (!hd)
				hd = hd1;
			else {

				tl->right_node = hd1;
				hd1->left_node = tl;
			}

			tl = hd1;
			hd1 = hd1->right_node;
		}

		else {

			if (!hd)
				hd = hd2;
			else {
				tl->right_node = hd2;
				hd2->left_node = tl;
			}

			tl = hd2;
			hd2 = hd2->right_node;
		}
	}

	while (hd1) {
		tl->right_node = hd1;
		hd1->left_node = tl;
		tl = hd1;
		hd1 = hd1->right_node;
	}

	while (hd2) {
		tl->right_node = hd2;
		hd2->left_node = tl;
		tl = hd2;
		hd2 = hd2->right_node;
	}

	// Return the created DLL
	return hd;
}

// list to bst conversion function
Node* sortedListToBST(Node*& hd, int y)
{
	// if hd is null or left node is not an element
	if (y <= 0 || !hd)
		return NULL;

	// Recursively create the left node component from the list
	Node* left_node = sortedListToBST(hd, y / 2);

	Node* rt = hd;
	rt->left_node = left_node;
	hd = hd->right_node;

	// Create the left node part recursively from the list
	rt->right_node = sortedListToBST(hd, y - (y / 2) - 1);

	// Return the rt of BST
	return rt;
}

// Two balanced BSTs are combined by this function
Node* mergeTrees(Node* rt1, Node* rt2, int x, int y)
{
	// Create sorted Doubly Linked Lists from BSTs

	Node* hd1 = NULL;
	bstreeTodllist(rt1, hd1);
	hd1->left_node = NULL;

	Node* hd2 = NULL;
	bstreeTodllist(rt2, hd2);
	hd2->left_node = NULL;

	// Combine the two sorted lists into a single one
	Node* hd = mergedLinkedList(hd1, hd2);

	// Make a tree out of the combined lists
	return sortedListToBST(hd, x + y);
}

void printInorder(Node* nodes)
{
	// if current node is NULL
	if (!nodes) {
		return;
	}

	printInorder(nodes->left_node);

	// current value's nodes in print
	cout << nodes->val << " ";

	printInorder(nodes->right_node);
}

/* Driver code*/
int main()
{
	/* Create following tree as first balanced BST
	110
	/ \
	60 400
	/ \
	10 90 */

	Node* rt1 = newNode(110);
	rt1->left_node = newNode(60);
	rt1->right_node = newNode(400);
	rt1->left_node->left_node = newNode(10);
	rt1->left_node->right_node = newNode(90);
	/* Create following tree as second balanced BST
			100
			/ \
		30 130
	*/
	Node* rt2 = newNode(100);
	rt2->left_node = newNode(30);
	rt2->right_node = newNode(130);

	// Function Call
	Node* mergedTree = mergeTrees(rt1, rt2, 5, 3);

	cout << "The merged data is traversed "
			"tree in order as shown below \n";
	printInorder(mergedTree);

	return 0;
}

Output:

Output

The merged data is traversed tree in order as shown below 
10 30 60 90 100 110 130 400

The time complexity is O(N + M), where N and M represent the number of nodes in the specified trees.

Auxiliary Space : O(1), as there is consistently additional space available.

Input Required

This code uses input(). Please provide values below: