Merge Two Balanced Binary Search Trees

Last Updated : 08 Oct, 2023

You are given two balanced binary search trees e.g., AVL or Red-Black Tree. Write a function that merges the two given balanced BSTs into a balanced binary search tree. Let there be m elements in the first tree and n elements in the other tree. Your merge function should take O(m+n) time.
In the following solutions, it is assumed that the sizes of trees are also given as input. If the size is not given, then we can get the size by traversing the tree (See this).

Method 1 (Insert elements of the first tree to the second):

Take all elements of the first BST one by one, and insert them into the second BST. Inserting an element to a self-balancing BST takes Logn time (See this) where n is the size of the BST. So time complexity of this method is Log(n) + Log(n+1) … Log(m+n-1). The value of this expression will be between mLogn and mLog(m+n-1). As an optimization, we can pick the smaller tree as the first tree.

Method 2 (Merge Inorder Traversals):

Do inorder traversal of the first tree and store the traversal in one temp array arr1[]. This step takes O(m) time.
Do inorder traversal of the second tree and store the traversal in another temp array arr2[]. This step takes O(n) time.
The arrays created in steps 1 and 2 are sorted arrays. Merge the two sorted arrays into one array of size m + n. This step takes O(m+n) time.
Construct a balanced tree from the merged array using the technique discussed in this post. This step takes O(m+n) time.

The time complexity of this method is O(m+n) which is better than method 1. This method takes O(m+n) time even if the input BSTs are not balanced.
Following is the implementation of this method.

C++

// C++ program to Merge Two Balanced Binary Search Trees 
#include<bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child 
and a pointer to right child */
class node 
{ 
    public:
    int data; 
    node* left; 
    node* right; 
}; 
 
// A utility function to merge two sorted arrays into one 
int *merge(int arr1[], int arr2[], int m, int n); 
 
// A helper function that stores inorder
// traversal of a tree in inorder array 
void storeInorder(node* node, int inorder[],
                            int *index_ptr); 
 
/* A function that constructs Balanced
Binary Search Tree from a sorted array 
See https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ */
node* sortedArrayToBST(int arr[], int start, int end); 
 
/* This function merges two balanced 
BSTs with roots as root1 and root2. 
m and n are the sizes of the trees respectively */
node* mergeTrees(node *root1, node *root2, int m, int n) 
{ 
    // Store inorder traversal of 
    // first tree in an array arr1[] 
    int *arr1 = new int[m]; 
    int i = 0; 
    storeInorder(root1, arr1, &i); 
 
    // Store inorder traversal of second
    // tree in another array arr2[] 
    int *arr2 = new int[n]; 
    int j = 0; 
    storeInorder(root2, arr2, &j); 
 
    // Merge the two sorted array into one 
    int *mergedArr = merge(arr1, arr2, m, n); 
 
    // Construct a tree from the merged 
    // array and return root of the tree 
    return sortedArrayToBST (mergedArr, 0, m + n - 1); 
} 
 
/* Helper function that allocates
a new node with the given data and 
NULL left and right pointers. */
node* newNode(int data) 
{ 
    node* Node = new node();
    Node->data = data; 
    Node->left = NULL; 
    Node->right = NULL; 
 
    return(Node); 
} 
 
// A utility function to print inorder
// traversal of a given binary tree 
void printInorder(node* node) 
{ 
    if (node == NULL) 
        return; 
 
    /* first recur on left child */
    printInorder(node->left); 
 
    cout << node->data << " "; 
 
    /* now recur on right child */
    printInorder(node->right); 
} 
 
// A utility function to merge
// two sorted arrays into one 
int *merge(int arr1[], int arr2[], int m, int n) 
{ 
    // mergedArr[] is going to contain result 
    int *mergedArr = new int[m + n]; 
    int i = 0, j = 0, k = 0; 
 
    // Traverse through both arrays 
    while (i < m && j < n) 
    { 
        // Pick the smaller element and put it in mergedArr 
        if (arr1[i] < arr2[j]) 
        { 
            mergedArr[k] = arr1[i]; 
            i++; 
        } 
        else
        { 
            mergedArr[k] = arr2[j]; 
            j++; 
        } 
        k++; 
    } 
 
    // If there are more elements in first array 
    while (i < m) 
    { 
        mergedArr[k] = arr1[i]; 
        i++; k++; 
    } 
 
    // If there are more elements in second array 
    while (j < n) 
    { 
        mergedArr[k] = arr2[j]; 
        j++; k++; 
    } 
 
    return mergedArr; 
} 
 
// A helper function that stores inorder
// traversal of a tree rooted with node 
void storeInorder(node* node, int inorder[], int *index_ptr) 
{ 
    if (node == NULL) 
        return; 
 
    /* first recur on left child */
    storeInorder(node->left, inorder, index_ptr); 
 
    inorder[*index_ptr] = node->data; 
    (*index_ptr)++; // increase index for next entry 
 
    /* now recur on right child */
    storeInorder(node->right, inorder, index_ptr); 
} 
 
/* A function that constructs Balanced 
// Binary Search Tree from a sorted array 
See https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ */
node* sortedArrayToBST(int arr[], int start, int end) 
{ 
    /* Base Case */
    if (start > end) 
    return NULL; 
 
    /* Get the middle element and make it root */
    int mid = (start + end)/2; 
    node *root = newNode(arr[mid]); 
 
    /* Recursively construct the left subtree and make it 
    left child of root */
    root->left = sortedArrayToBST(arr, start, mid-1); 
 
    /* Recursively construct the right subtree and make it 
    right child of root */
    root->right = sortedArrayToBST(arr, mid+1, end); 
 
    return root; 
} 
 
/* Driver code*/
int main() 
{ 
    /* Create following tree as first balanced BST 
        100 
        / \ 
        50 300 
    / \ 
    20 70 
    */
    node *root1 = newNode(100); 
    root1->left     = newNode(50); 
    root1->right = newNode(300); 
    root1->left->left = newNode(20); 
    root1->left->right = newNode(70); 
 
    /* Create following tree as second balanced BST 
            80 
        / \ 
        40 120 
    */
    node *root2 = newNode(80); 
    root2->left     = newNode(40); 
    root2->right = newNode(120); 
 
    node *mergedTree = mergeTrees(root1, root2, 5, 3); 
 
    cout << "Following is Inorder traversal of the merged tree \n"; 
    printInorder(mergedTree); 
 
    return 0; 
} 
 
// This code is contributed by rathbhupendra

C

// C program to Merge Two Balanced Binary Search Trees
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
 
// A utility function to merge two sorted arrays into one
int *merge(int arr1[], int arr2[], int m, int n);
 
// A helper function that stores inorder traversal of a tree in inorder array
void storeInorder(struct node* node, int inorder[], int *index_ptr);
 
/* A function that constructs Balanced Binary Search Tree from a sorted array
   See https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ */
struct node* sortedArrayToBST(int arr[], int start, int end);
 
/* This function merges two balanced BSTs with roots as root1 and root2.
   m and n are the sizes of the trees respectively */
struct node* mergeTrees(struct node *root1, struct node *root2, int m, int n)
{
    // Store inorder traversal of first tree in an array arr1[]
    int *arr1 = new int[m];
    int i = 0;
    storeInorder(root1, arr1, &i);
 
    // Store inorder traversal of second tree in another array arr2[]
    int *arr2 = new int[n];
    int j = 0;
    storeInorder(root2, arr2, &j);
 
    // Merge the two sorted array into one
    int *mergedArr = merge(arr1, arr2, m, n);
 
    // Construct a tree from the merged array and return root of the tree
    return sortedArrayToBST (mergedArr, 0, m+n-1);
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return(node);
}
 
// A utility function to print inorder traversal of a given binary tree
void printInorder(struct node* node)
{
    if (node == NULL)
        return;
 
    /* first recur on left child */
    printInorder(node->left);
 
    printf("%d ", node->data);
 
    /* now recur on right child */
    printInorder(node->right);
}
 
// A utility function to merge two sorted arrays into one
int *merge(int arr1[], int arr2[], int m, int n)
{
    // mergedArr[] is going to contain result
    int *mergedArr = new int[m + n];
    int i = 0, j = 0, k = 0;
 
    // Traverse through both arrays
    while (i < m && j < n)
    {
        // Pick the smaller element and put it in mergedArr
        if (arr1[i] < arr2[j])
        {
            mergedArr[k] = arr1[i];
            i++;
        }
        else
        {
            mergedArr[k] = arr2[j];
            j++;
        }
        k++;
    }
 
    // If there are more elements in first array
    while (i < m)
    {
        mergedArr[k] = arr1[i];
        i++; k++;
    }
 
    // If there are more elements in second array
    while (j < n)
    {
        mergedArr[k] = arr2[j];
        j++; k++;
    }
 
    return mergedArr;
}
 
// A helper function that stores inorder traversal of a tree rooted with node
void storeInorder(struct node* node, int inorder[], int *index_ptr)
{
    if (node == NULL)
        return;
 
    /* first recur on left child */
    storeInorder(node->left, inorder, index_ptr);
 
    inorder[*index_ptr] = node->data;
    (*index_ptr)++;  // increase index for next entry
 
    /* now recur on right child */
    storeInorder(node->right, inorder, index_ptr);
}
 
/* A function that constructs Balanced Binary Search Tree from a sorted array
   See https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ */
struct node* sortedArrayToBST(int arr[], int start, int end)
{
    /* Base Case */
    if (start > end)
      return NULL;
 
    /* Get the middle element and make it root */
    int mid = (start + end)/2;
    struct node *root = newNode(arr[mid]);
 
    /* Recursively construct the left subtree and make it
       left child of root */
    root->left =  sortedArrayToBST(arr, start, mid-1);
 
    /* Recursively construct the right subtree and make it
       right child of root */
    root->right = sortedArrayToBST(arr, mid+1, end);
 
    return root;
}
 
/* Driver program to test above functions*/
int main()
{
    /* Create following tree as first balanced BST
           100
          /  \
        50    300
       / \
      20  70
    */
    struct node *root1  = newNode(100);
    root1->left         = newNode(50);
    root1->right        = newNode(300);
    root1->left->left   = newNode(20);
    root1->left->right  = newNode(70);
 
    /* Create following tree as second balanced BST
            80
           /  \
         40   120
    */
    struct node *root2  = newNode(80);
    root2->left         = newNode(40);
    root2->right        = newNode(120);
 
    struct node *mergedTree = mergeTrees(root1, root2, 5, 3);
 
    printf ("Following is Inorder traversal of the merged tree \n");
    printInorder(mergedTree);
 
    getchar();
    return 0;
}

Java

// Java program to Merge Two Balanced Binary Search Trees
import java.io.*;
import java.util.ArrayList;
 
// A binary tree node
class Node {
     
    int data;
    Node left, right;
     
    Node(int d) {
        data = d;
        left = right = null;
    }
}
 
class BinarySearchTree
{
     
    // Root of BST
    Node root;
 
    // Constructor
    BinarySearchTree() { 
        root = null; 
    }
     
    // Inorder traversal of the tree
    void inorder()
    {
        inorderUtil(this.root);
    }
     
// Utility function for inorder traversal of the tree
void inorderUtil(Node node)
{
    if(node==null)
        return;
         
    inorderUtil(node.left);
    System.out.print(node.data + " ");
    inorderUtil(node.right);
}
     
 
    // A Utility Method that stores inorder traversal of a tree
    public ArrayList<Integer> storeInorderUtil(Node node, ArrayList<Integer> list)
    {
        if(node == null)
            return list;
         
        //recur on the left child
        storeInorderUtil(node.left, list);
         
        // Adds data to the list
        list.add(node.data);
         
        //recur on the right child
        storeInorderUtil(node.right, list);
         
        return list;
    }
     
    // Method that stores inorder traversal of a tree
    ArrayList<Integer> storeInorder(Node node)
    {
        ArrayList<Integer> list1 = new ArrayList<>(); 
        ArrayList<Integer> list2 = storeInorderUtil(node,list1); 
        return list2;
    }
 
    // Method that merges two ArrayLists into one. 
    ArrayList<Integer> merge(ArrayList<Integer>list1, ArrayList<Integer>list2, int m, int n)
    {
        // list3 will contain the merge of list1 and list2
        ArrayList<Integer> list3 = new ArrayList<>();
        int i=0;
        int j=0;
         
        //Traversing through both ArrayLists
        while( i<m && j<n)
        {
            // Smaller one goes into list3
            if(list1.get(i)<list2.get(j))
            {
                list3.add(list1.get(i));
                i++;
            }
            else
            {
                list3.add(list2.get(j));
                j++;
            }
        }
         
        // Adds the remaining elements of list1 into list3
        while(i<m)
        {
            list3.add(list1.get(i));
            i++;
        }
     
        // Adds the remaining elements of list2 into list3
        while(j<n)
        {
            list3.add(list2.get(j));
            j++;
        }
        return list3;
    }
     
    // Method that converts an ArrayList to a BST
    Node ALtoBST(ArrayList<Integer>list, int start, int end)
    {
        // Base case
        if(start > end)
            return null;
     
        // Get the middle element and make it root     
        int mid = (start+end)/2;
        Node node = new Node(list.get(mid));
 
        /* Recursively construct the left subtree and make it
        left child of root */
        node.left = ALtoBST(list, start, mid-1);
         
        /* Recursively construct the right subtree and make it
        right child of root */
        node.right = ALtoBST(list, mid+1, end);
     
    return node;
    }
     
    // Method that merges two trees into a single one. 
    Node mergeTrees(Node node1, Node node2)
    {
        //Stores Inorder of tree1 to list1
        ArrayList<Integer>list1 = storeInorder(node1);
         
        //Stores Inorder of tree2 to list2
        ArrayList<Integer>list2 = storeInorder(node2);
         
        // Merges both list1 and list2 into list3
        ArrayList<Integer>list3 = merge(list1, list2, list1.size(), list2.size());
         
        //Eventually converts the merged list into resultant BST
        Node node = ALtoBST(list3, 0, list3.size()-1);
        return node;
    }
 
    // Driver function
    public static void main (String[] args)
    {
         
        /* Creating following tree as First balanced BST
                100
                / \
                50 300
                / \
               20 70
        */
         
        BinarySearchTree tree1 = new BinarySearchTree();
        tree1.root = new Node(100);
        tree1.root.left = new Node(50);
        tree1.root.right = new Node(300);
        tree1.root.left.left = new Node(20);
        tree1.root.left.right = new Node(70);
         
        /* Creating following tree as second balanced BST
                80
                / \
              40 120
        */
             
        BinarySearchTree tree2 = new BinarySearchTree();
        tree2.root = new Node(80);    
        tree2.root.left = new Node(40);
        tree2.root.right = new Node(120);
             
             
        BinarySearchTree tree = new BinarySearchTree();    
        tree.root = tree.mergeTrees(tree1.root, tree2.root);
        System.out.println("The Inorder traversal of the merged BST is: ");
        tree.inorder();
    }
}
// This code has been contributed by Kamal Rawal

Python3

# A binary tree node has data, pointer to left child  
# and a pointer to right child
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
# A utility function to merge two sorted arrays into one
# Time Complexity of below function: O(m + n)
# Space Complexity of below function: O(m + n)
def merge_sorted_arr(arr1, arr2):
    arr = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            arr.append(arr1[i])
            i += 1
        else:
            arr.append(arr2[j])
            j += 1
    while i < len(arr1):
        arr.append(arr1[i])
        i += 1
    while i < len(arr2):
        arr.append(arr2[j])
        j += 1
    return arr
 
# A helper function that stores inorder
# traversal of a tree in arr
def inorder(root, arr = []):
    if root:
        inorder(root.left, arr)
        arr.append(root.val)
        inorder(root.right, arr)
 
# A utility function to insert the values
# in the individual Tree
def insert(root, val):
    if not root:
        return Node(val)
    if root.val == val:
        return root
    elif root.val > val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root
 
# Converts the merged array to a balanced BST
# Explanation of the below code:
# https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
def arr_to_bst(arr):
    if not arr:
        return None
    mid = len(arr) // 2
    root = Node(arr[mid])
    root.left = arr_to_bst(arr[:mid])
    root.right = arr_to_bst(arr[mid + 1:])
    return root
 
if __name__=='__main__':
    root1 = root2 = None
     
    # Inserting values in first tree
    root1 = insert(root1, 100)
    root1 = insert(root1, 50)
    root1 = insert(root1, 300)
    root1 = insert(root1, 20)
    root1 = insert(root1, 70)
     
    # Inserting values in second tree
    root2 = insert(root2, 80)
    root2 = insert(root2, 40)
    root2 = insert(root2, 120)
    arr1 = []
    inorder(root1, arr1)
    arr2 = []
    inorder(root2, arr2)
    arr = merge_sorted_arr(arr1, arr2)
    root = arr_to_bst(arr)
    res = []
    inorder(root, res)
    print('Following is Inorder traversal of the merged tree')
    for i in res:
      print(i, end = ' ')
       
# This code is contributed by Flarow4

C#

// C# program to Merge Two Balanced Binary Search Trees
using System;
using System.Collections.Generic;
 
// A binary tree node 
public class Node
{
 
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class BinarySearchTree
{
 
    // Root of BST 
    public Node root;
 
    // Constructor 
    public BinarySearchTree()
    {
        root = null;
    }
 
    // Inorder traversal of the tree 
    public virtual void inorder()
    {
        inorderUtil(this.root);
    }
 
// Utility function for inorder traversal of the tree 
public virtual void inorderUtil(Node node)
{
    if (node == null)
    {
        return;
    }
 
    inorderUtil(node.left);
    Console.Write(node.data + " ");
    inorderUtil(node.right);
}
 
 
    // A Utility Method that stores inorder traversal of a tree 
    public virtual List<int> storeInorderUtil(Node node, List<int> list)
    {
        if (node == null)
        {
            return list;
        }
 
        //recur on the left child 
        storeInorderUtil(node.left, list);
 
        // Adds data to the list 
        list.Add(node.data);
 
        //recur on the right child 
        storeInorderUtil(node.right, list);
 
        return list;
    }
 
    // Method that stores inorder traversal of a tree 
    public virtual List<int> storeInorder(Node node)
    {
        List<int> list1 = new List<int>();
        List<int> list2 = storeInorderUtil(node,list1);
        return list2;
    }
 
    // Method that merges two ArrayLists into one.  
    public virtual List<int> merge(List<int> list1, List<int> list2, int m, int n)
    {
        // list3 will contain the merge of list1 and list2 
        List<int> list3 = new List<int>();
        int i = 0;
        int j = 0;
 
        //Traversing through both ArrayLists 
        while (i < m && j < n)
        {
            // Smaller one goes into list3 
            if (list1[i] < list2[j])
            {
                list3.Add(list1[i]);
                i++;
            }
            else
            {
                list3.Add(list2[j]);
                j++;
            }
        }
 
        // Adds the remaining elements of list1 into list3 
        while (i < m)
        {
            list3.Add(list1[i]);
            i++;
        }
 
        // Adds the remaining elements of list2 into list3 
        while (j < n)
        {
            list3.Add(list2[j]);
            j++;
        }
        return list3;
    }
 
    // Method that converts an ArrayList to a BST 
    public virtual Node ALtoBST(List<int> list, int start, int end)
    {
        // Base case 
        if (start > end)
        {
            return null;
        }
 
        // Get the middle element and make it root      
        int mid = (start + end) / 2;
        Node node = new Node(list[mid]);
 
        /* Recursively construct the left subtree and make it 
        left child of root */
        node.left = ALtoBST(list, start, mid - 1);
 
        /* Recursively construct the right subtree and make it 
        right child of root */
        node.right = ALtoBST(list, mid + 1, end);
 
    return node;
    }
 
    // Method that merges two trees into a single one.  
    public virtual Node mergeTrees(Node node1, Node node2)
    {
        //Stores Inorder of tree1 to list1 
        List<int> list1 = storeInorder(node1);
 
        //Stores Inorder of tree2 to list2 
        List<int> list2 = storeInorder(node2);
 
        // Merges both list1 and list2 into list3 
        List<int> list3 = merge(list1, list2, list1.Count, list2.Count);
 
        //Eventually converts the merged list into resultant BST 
        Node node = ALtoBST(list3, 0, list3.Count - 1);
        return node;
    }
 
    // Driver function 
    public static void Main(string[] args)
    {
 
        /* Creating following tree as First balanced BST 
                100 
                / \ 
                50 300 
                / \ 
               20 70 
        */
 
        BinarySearchTree tree1 = new BinarySearchTree();
        tree1.root = new Node(100);
        tree1.root.left = new Node(50);
        tree1.root.right = new Node(300);
        tree1.root.left.left = new Node(20);
        tree1.root.left.right = new Node(70);
 
        /* Creating following tree as second balanced BST 
                80 
                / \ 
              40 120 
        */
 
        BinarySearchTree tree2 = new BinarySearchTree();
        tree2.root = new Node(80);
        tree2.root.left = new Node(40);
        tree2.root.right = new Node(120);
 
 
        BinarySearchTree tree = new BinarySearchTree();
        tree.root = tree.mergeTrees(tree1.root, tree2.root);
        Console.WriteLine("The Inorder traversal of the merged BST is: ");
        tree.inorder();
    }
}
 
  // This code is contributed by Shrikant13

Javascript

<script>
 
      // JavaScript program to Merge Two 
      // Balanced Binary Search Trees
      // A binary tree node
      class Node {
        constructor(d) {
          this.data = d;
          this.left = null;
          this.right = null;
        }
      }
 
      class BinarySearchTree {
        // Constructor
        constructor() {
          this.root = null;
        }
 
        // Inorder traversal of the tree
        inorder() {
          this.inorderUtil(this.root);
        }
 
        // Utility function for inorder traversal of the tree
        inorderUtil(node) {
          if (node == null) {
            return;
          }
 
          this.inorderUtil(node.left);
          document.write(node.data + " ");
          this.inorderUtil(node.right);
        }
 
        // A Utility Method that stores 
        // inorder traversal of a tree
        storeInorderUtil(node, list) {
          if (node == null) {
            return list;
          }
 
          //recur on the left child
          this.storeInorderUtil(node.left, list);
 
          // Adds data to the list
          list.push(node.data);
 
          //recur on the right child
          this.storeInorderUtil(node.right, list);
 
          return list;
        }
 
        // Method that stores inorder traversal of a tree
        storeInorder(node) {
          var list1 = [];
          var list2 = this.storeInorderUtil(node, list1);
          return list2;
        }
 
        // Method that merges two ArrayLists into one.
        merge(list1, list2, m, n) {
          // list3 will contain the merge of list1 and list2
          var list3 = [];
          var i = 0;
          var j = 0;
 
          //Traversing through both ArrayLists
          while (i < m && j < n) {
            // Smaller one goes into list3
            if (list1[i] < list2[j]) {
              list3.push(list1[i]);
              i++;
            } else {
              list3.push(list2[j]);
              j++;
            }
          }
 
          // Adds the remaining elements of list1 into list3
          while (i < m) {
            list3.push(list1[i]);
            i++;
          }
 
          // Adds the remaining elements of list2 into list3
          while (j < n) {
            list3.push(list2[j]);
            j++;
          }
          return list3;
        }
 
        // Method that converts an ArrayList to a BST
        ALtoBST(list, start, end) {
          // Base case
          if (start > end) {
            return null;
          }
 
          // Get the middle element and make it root
          var mid = parseInt((start + end) / 2);
          var node = new Node(list[mid]);
 
          /* Recursively construct the left subtree and make it
        left child of root */
          node.left = this.ALtoBST(list, start, mid - 1);
 
          /* Recursively construct the right subtree and make it
        right child of root */
          node.right = this.ALtoBST(list, mid + 1, end);
 
          return node;
        }
 
        // Method that merges two trees into a single one.
        mergeTrees(node1, node2) {
          //Stores Inorder of tree1 to list1
          var list1 = this.storeInorder(node1);
 
          //Stores Inorder of tree2 to list2
          var list2 = this.storeInorder(node2);
 
          // Merges both list1 and list2 into list3
          var list3 = 
          this.merge(list1, list2, list1.length, list2.length);
 
          //Eventually converts the merged list into resultant BST
          var node = this.ALtoBST(list3, 0, list3.length - 1);
          return node;
        }
      }
      // Driver function
      /* Creating following tree as First balanced BST
                100
                / \
                50 300
                / \
            20 70
        */
 
      var tree1 = new BinarySearchTree();
      tree1.root = new Node(100);
      tree1.root.left = new Node(50);
      tree1.root.right = new Node(300);
      tree1.root.left.left = new Node(20);
      tree1.root.left.right = new Node(70);
 
      /* Creating following tree as second balanced BST
                80
                / \
            40 120
        */
 
      var tree2 = new BinarySearchTree();
      tree2.root = new Node(80);
      tree2.root.left = new Node(40);
      tree2.root.right = new Node(120);
 
      var tree = new BinarySearchTree();
      tree.root = tree.mergeTrees(tree1.root, tree2.root);
      document.write(
      "Following is Inorder traversal of the merged tree <br>"
      );
      tree.inorder();
       
</script>

Output

Following is Inorder traversal of the merged tree 
20 40 50 70 80 100 120 300

Time complexity: O(m+n), where m and n are the numbers of elements in the two binary search trees.
Space complexity: O(m+n). This is because we need to allocate space for the two arrays that store the elements from the two binary search trees, as well as an array to store the merged elements.

Method 3 (In-Place Merge using DLL):

We can use a Doubly Linked List to merge trees in place. Following are the steps.

Convert the given two Binary Search Trees into a doubly linked list in place (Refer to this post for this step).
Merge the two sorted Linked Lists (Refer to this post for this step).
Build a Balanced Binary Search Tree from the merged list created in step 2. (Refer to this post for this step)

The time complexity of this method is also O(m+n) and this method does conversion in place.
Thanks to Dheeraj and Ronzii for suggesting this method.

C++

// C++ Code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data,
a pointer to left child
and a pointer to right child */
class Node {
public:
    int data;
    Node* left;
    Node* right;
};
 
// Function to return a new Node
Node* newNode(int data)
{
    Node* node = new Node();
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
// Function to convert bst to
// a doubly linked list
void bstTodll(Node* root, Node*& head)
{
    // if root is NULL
    if (!root)
        return;
 
    // Convert right subtree recursively
    bstTodll(root->right, head);
 
    // Update root
    root->right = head;
 
    // if head is not NULL
    if (head) {
 
        // Update left of the head
        head->left = root;
    }
 
    // Update head
    head = root;
 
    // Convert left subtree recursively
    bstTodll(root->left, head);
}
 
// Function to merge two sorted linked list
Node* mergeLinkedList(Node* head1, Node* head2)
{
 
    /*Create head and tail for result list*/
    Node* head = NULL;
    Node* tail = NULL;
 
    while (head1 && head2) {
 
        if (head1->data < head2->data) {
 
            if (!head)
                head = head1;
            else {
 
                tail->right = head1;
                head1->left = tail;
            }
 
            tail = head1;
            head1 = head1->right;
        }
 
        else {
 
            if (!head)
                head = head2;
            else {
                tail->right = head2;
                head2->left = tail;
            }
 
            tail = head2;
            head2 = head2->right;
        }
    }
 
    while (head1) {
        tail->right = head1;
        head1->left = tail;
        tail = head1;
        head1 = head1->right;
    }
 
    while (head2) {
        tail->right = head2;
        head2->left = tail;
        tail = head2;
        head2 = head2->right;
    }
 
    // Return the created DLL
    return head;
}
 
// function to convert list to bst
Node* sortedListToBST(Node*& head, int n)
{
    // if no element is left or head is null
    if (n <= 0 || !head)
        return NULL;
 
    // Create left part from the list recursively
    Node* left = sortedListToBST(head, n / 2);
 
    Node* root = head;
    root->left = left;
    head = head->right;
 
    // Create left part from the list recursively
    root->right = sortedListToBST(head, n - (n / 2) - 1);
 
    // Return the root of BST
    return root;
}
 
// This function merges two balanced BSTs
Node* mergeTrees(Node* root1, Node* root2, int m, int n)
{
    // Convert BSTs into sorted Doubly Linked Lists
 
    Node* head1 = NULL;
    bstTodll(root1, head1);
    head1->left = NULL;
 
    Node* head2 = NULL;
    bstTodll(root2, head2);
    head2->left = NULL;
 
    // Merge the two sorted lists into one
    Node* head = mergeLinkedList(head1, head2);
 
    // Construct a tree from the merged lists
    return sortedListToBST(head, m + n);
}
 
void printInorder(Node* node)
{
    // if current node is NULL
    if (!node) {
        return;
    }
 
    printInorder(node->left);
 
      // Print node of current data
    cout << node->data << " ";
 
    printInorder(node->right);
}
 
/* Driver code*/
int main()
{
    /* Create following tree as first balanced BST
       100
       / \
      50 300
     / \
    20 70   */
 
    Node* root1 = newNode(100);
    root1->left = newNode(50);
    root1->right = newNode(300);
    root1->left->left = newNode(20);
    root1->left->right = newNode(70);
 
    /* Create following tree as second balanced BST
             80
            / \
           40 120
    */
    Node* root2 = newNode(80);
    root2->left = newNode(40);
    root2->right = newNode(120);
 
      // Function Call
    Node* mergedTree = mergeTrees(root1, root2, 5, 3);
 
    cout << "Following is Inorder traversal of the merged "
            "tree \n";
    printInorder(mergedTree);
 
    return 0;
}
 
// This code is contributed by Tapesh(tapeshdua420)

Java

// Java Code for the above approach
import java.util.*;
 
/* A binary tree node has data,
a pointer to left child
and a pointer to right child */
class Node {
    int data;
    Node left, right;
 
    Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
// Function to return a new Node
public class Main {
 
    Node newNode(int data)
    {
        Node node = new Node(data);
        node.left = null;
        node.right = null;
        return (node);
    }
 
    // Function to convert bst to a doubly linked list
    void bstTodll(Node root, Node[] head)
    {
 
        // if root is NULL
        if (root == null)
            return;
 
        // Convert right subtree recursively
        bstTodll(root.right, head);
 
        // Update root
        root.right = head[0];
 
        // if head is not NULL
        if (head[0] != null) {
 
            // Update left of the head
            head[0].left = root;
        }
 
        // Update head
        head[0] = root;
 
        // Convert left subtree recursively
        bstTodll(root.left, head);
    }
 
    // Function to merge two sorted linked list
    Node mergeLinkedList(Node head1, Node head2)
    {
 
        /*Create head and tail for result list*/
        Node head = null, tail = null;
        while (head1 != null && head2 != null) {
            if (head1.data < head2.data) {
                if (head == null) {
                    head = head1;
                }
                else {
                    tail.right = head1;
                    head1.left = tail;
                }
                tail = head1;
                head1 = head1.right;
            }
            else {
                if (head == null) {
                    head = head2;
                }
                else {
                    tail.right = head2;
                    head2.left = tail;
                }
                tail = head2;
                head2 = head2.right;
            }
        }
        while (head1 != null) {
            tail.right = head1;
            head1.left = tail;
            tail = head1;
            head1 = head1.right;
        }
        while (head2 != null) {
            tail.right = head2;
            head2.left = tail;
            tail = head2;
            head2 = head2.right;
        }
 
        // Return the created DLL
        return head;
    }
 
    // function to convert list to bst
    Node sortedListToBST(Node[] head, int n)
    {
 
        // if no element is left or head is null
        if (n <= 0 || head[0] == null)
            return null;
 
        // Create left part from the list recursively
        Node left = sortedListToBST(head, n / 2);
        Node root = head[0];
        root.left = left;
        head[0] = head[0].right;
 
        // Create left part from the list recursively
        root.right = sortedListToBST(head, n - (n / 2) - 1);
 
        // Return the root of BST
        return root;
    }
 
    // This function merges two balanced BSTs
    Node mergeTrees(Node root1, Node root2, int m, int n)
    {
 
        // Convert BSTs into sorted Doubly Linked Lists
 
        Node[] head1 = new Node[1];
        head1[0] = null;
        bstTodll(root1, head1);
        head1[0].left = null;
 
        Node[] head2 = new Node[1];
        head2[0] = null;
        bstTodll(root2, head2);
        head2[0].left = null;
 
        // Merge the two sorted lists into one
        Node head = mergeLinkedList(head1[0], head2[0]);
 
        // Construct a tree from the merged lists
        return sortedListToBST(new Node[] { head }, m + n);
    }
 
    void printInorder(Node node)
    {
 
        // if current node is NULL
        if (node == null) {
            return;
        }
        printInorder(node.left);
 
        // Print node of current data
        System.out.print(node.data + " ");
 
        printInorder(node.right);
    }
 
    /* Driver code*/
    public static void main(String[] args)
    {
        Main obj = new Main();
 
        /* Create following tree as first balanced BST
           100
           / \
          50 300
         / \
        20 70   */
 
        Node root1 = obj.newNode(100);
        root1.left = obj.newNode(50);
        root1.right = obj.newNode(300);
        root1.left.left = obj.newNode(20);
        root1.left.right = obj.newNode(70);
 
        /* Create following tree as second balanced BST
                80
               / \
              40 120
       */
 
        Node root2 = obj.newNode(80);
        root2.left = obj.newNode(40);
        root2.right = obj.newNode(120);
 
        // Function Call
        Node mergedTree
            = obj.mergeTrees(root1, root2, 5, 3);
 
        System.out.println(
            "Following is Inorder traversal of the merged tree:");
        obj.printInorder(mergedTree);
    }
}

Python

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
class Solution:
    def __init__(self):
        self.head1 = [None]
        self.head2 = [None]
 
    def newNode(self, data):
        node = TreeNode(data)
        node.left = None
        node.right = None
        return node
 
    def bstToDLL(self, root, head):
        if not root:
            return
 
        self.bstToDLL(root.right, head)
 
        root.right = head[0]
 
        if head[0]:
            head[0].left = root
 
        head[0] = root
 
        self.bstToDLL(root.left, head)
 
    def mergeLinkedList(self, head1, head2):
        head = None
        tail = None
 
        while head1 and head2:
            if head1.data < head2.data:
                if not head:
                    head = head1
                else:
                    tail.right = head1
                    head1.left = tail
                tail = head1
                head1 = head1.right
            else:
                if not head:
                    head = head2
                else:
                    tail.right = head2
                    head2.left = tail
                tail = head2
                head2 = head2.right
 
        while head1:
            tail.right = head1
            head1.left = tail
            tail = head1
            head1 = head1.right
 
        while head2:
            tail.right = head2
            head2.left = tail
            tail = head2
            head2 = head2.right
 
        return head
 
    def sortedListToBST(self, head, n):
        if n <= 0 or not head[0]:
            return None
 
        left = self.sortedListToBST(head, n // 2)
        root = head[0]
        root.left = left
        head[0] = head[0].right
 
        root.right = self.sortedListToBST(head, n - (n // 2) - 1)
 
        return root
 
    def mergeTrees(self, root1, root2, m, n):
        self.bstToDLL(root1, self.head1)
        self.head1[0].left = None
 
        self.bstToDLL(root2, self.head2)
        self.head2[0].left = None
 
        merged_head = self.mergeLinkedList(self.head1[0], self.head2[0])
 
        merged_root = self.sortedListToBST([merged_head], m + n)
 
        return merged_root
 
    def printInorder(self, node):
        if not node:
            return
        self.printInorder(node.left)
        print(node.data),
        self.printInorder(node.right)
 
# Create the first balanced BST
root1 = TreeNode(100)
root1.left = TreeNode(50)
root1.right = TreeNode(300)
root1.left.left = TreeNode(20)
root1.left.right = TreeNode(70)
 
# Create the second balanced BST
root2 = TreeNode(80)
root2.left = TreeNode(40)
root2.right = TreeNode(120)
 
solution = Solution()
mergedTree = solution.mergeTrees(root1, root2, 5, 3)
 
print("Inorder traversal of the merged tree:")
solution.printInorder(mergedTree)

C#

// C# Code for the above approach
using System;
 
/* A binary tree node has data,
a pointer to left child
and a pointer to right child */
public class Node {
  public int data;
  public Node left;
  public Node right;
}
 
public class Program {
  // Function to return a new Node
  static Node newNode(int data)
  {
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
 
    return node;
  }
 
  // Function to convert bst to
  // a doubly linked list
  static void bstTodll(Node root, ref Node head)
  {
    // if root is NUL
    if (root == null)
      return;
 
    // Convert right subtree recursively
    bstTodll(root.right, ref head);
 
    // Update root
    root.right = head;
 
    // if head is not NULL
    if (head != null)
 
      // Update left of the head
      head.left = root;
 
    // Update head
    head = root;
 
    // Convert left subtree recursively
    bstTodll(root.left, ref head);
  }
 
  // Function to merge two sorted linked list
  static Node mergeLinkedList(Node head1, Node head2)
  {
    /*Create head and tail for result list*/
    Node head = null, tail = null;
 
    while (head1 != null && head2 != null) {
      if (head1.data < head2.data) {
        if (head == null)
          head = head1;
        else {
          tail.right = head1;
          head1.left = tail;
        }
 
        tail = head1;
        head1 = head1.right;
      }
      else {
        if (head == null)
          head = head2;
        else {
          tail.right = head2;
          head2.left = tail;
        }
 
        tail = head2;
        head2 = head2.right;
      }
    }
 
    while (head1 != null) {
      tail.right = head1;
      head1.left = tail;
      tail = head1;
      head1 = head1.right;
    }
 
    while (head2 != null) {
      tail.right = head2;
      head2.left = tail;
      tail = head2;
      head2 = head2.right;
    }
 
    // Return the created DLL
    return head;
  }
 
  // function to convert list to bst
  static Node sortedListToBST(ref Node head, int n)
  {
    // if no element is left or head is null
    if (n <= 0 || head == null)
      return null;
    // Create left part from the list recursively
    Node left = sortedListToBST(ref head, n / 2);
 
    Node root = head;
    root.left = left;
    head = head.right;
 
    // Create left part from the list recursively
    root.right
      = sortedListToBST(ref head, n - (n / 2) - 1);
 
    // Return the root of BST
    return root;
  }
 
  // This function merges two balanced BSTs
 
  static Node mergeTrees(Node root1, Node root2, int m,
                         int n)
  {
    // Convert BSTs into sorted Doubly Linked Lists
    Node head1 = null;
    bstTodll(root1, ref head1);
    head1.left = null;
 
    Node head2 = null;
    bstTodll(root2, ref head2);
    head2.left = null;
 
    // Merge the two sorted lists into one
    Node head = mergeLinkedList(head1, head2);
 
    // Construct a tree from the merged lists
    return sortedListToBST(ref head, m + n);
  }
 
  static void printInorder(Node node)
  {
    // if current node is NULL
    if (node == null)
      return;
 
    printInorder(node.left);
 
    // Print node of current data
    Console.Write(node.data + " ");
    printInorder(node.right);
  }
 
  /* Driver code*/
  public static void Main()
  {
 
    /* Create following tree as first balanced BST
           100
           / \
          50 300
         / \
        20 70   */
    Node root1 = newNode(100);
    root1.left = newNode(50);
    root1.right = newNode(300);
    root1.left.left = newNode(20);
    root1.left.right = newNode(70);
 
    /* Create following tree as second balanced BST
                 80
                / \
               40 120
        */
    Node root2 = newNode(80);
    root2.left = newNode(40);
    root2.right = newNode(120);
 
    // Function Call
    Node mergedTree = mergeTrees(root1, root2, 5, 3);
 
    Console.WriteLine(
      "Following is Inorder traversal of the merged tree: ");
    printInorder(mergedTree);
  }
  // This code is contributed by rutikbhosale
}

Javascript

// JavaScrpit Code for above approach
 
// A binary tree node has data,
// a pointer to left child,
// and a pointer to right child
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// Function to convert BST to a doubly linked list
function bstToDll(root, headRef) {
    if (!root) {
        return;
    }
 
    // Convert right subtree recursively
    bstToDll(root.right, headRef);
 
    // Update root
    root.right = headRef.node;
 
    // Update left of the head if head is not null
    if (headRef.node) {
        headRef.node.left = root;
    }
 
    // Update head
    headRef.node = root;
 
    // Convert left subtree recursively
    bstToDll(root.left, headRef);
}
 
// Function to merge two sorted linked lists
function mergeLinkedList(head1, head2) {
    let head = null;
    let tail = null;
 
    while (head1 && head2) {
        if (head1.data < head2.data) {
            if (!head) {
                head = head1;
            } else {
                tail.right = head1;
                head1.left = tail;
            }
            tail = head1;
            head1 = head1.right;
        } else {
            if (!head) {
                head = head2;
            } else {
                tail.right = head2;
                head2.left = tail;
            }
            tail = head2;
            head2 = head2.right;
        }
    }
 
    while (head1) {
        tail.right = head1;
        head1.left = tail;
        tail = head1;
        head1 = head1.right;
    }
 
    while (head2) {
        tail.right = head2;
        head2.left = tail;
        tail = head2;
        head2 = head2.right;
    }
 
    // Return the created DLL
    return head;
}
 
// Function to convert a sorted linked list to a BST
function sortedListToBST(headRef, n) {
    if (n <= 0 || !headRef.node) {
        return null;
    }
 
    // Create the left part from the list recursively
    const left = sortedListToBST(headRef, Math.floor(n / 2));
 
    const root = headRef.node;
    root.left = left;
    headRef.node = headRef.node.right;
 
    // Create the right part from the list recursively
    root.right = sortedListToBST(headRef, n - Math.floor(n / 2) - 1);
 
    // Return the root of the BST
    return root;
}
 
// This function merges two balanced BSTs
function mergeTrees(root1, root2, m, n) {
    // Convert BSTs into sorted Doubly Linked Lists
    const headRef1 = { node: null };
    bstToDll(root1, headRef1);
    headRef1.node.left = null;
 
    const headRef2 = { node: null };
    bstToDll(root2, headRef2);
    headRef2.node.left = null;
 
    // Merge the two sorted lists into one
    const mergedHead = mergeLinkedList(headRef1.node, headRef2.node);
 
    // Construct a tree from the merged lists
    return sortedListToBST({ node: mergedHead }, m + n);
}
 
function printInorder(node) {
    if (!node) {
        return;
    }
 
    printInorder(node.left);
    console.log(node.data);
    printInorder(node.right);
}
 
// Driver code
// Create the first balanced BST
const root1 = new Node(100);
root1.left = new Node(50);
root1.right = new Node(300);
root1.left.left = new Node(20);
root1.left.right = new Node(70);
 
// Create the second balanced BST
const root2 = new Node(80);
root2.left = new Node(40);
root2.right = new Node(120);
 
// Function call to merge the trees
const mergedTree = mergeTrees(root1, root2, 5, 3);
 
console.log("Following is Inorder traversal of the merged tree:");
printInorder(mergedTree);

Output

Following is Inorder traversal of the merged tree 
20 40 50 70 80 100 120 300

Time Complexity: O(N + M). where N and M are the numbers of nodes in the given trees.
Auxiliary Space: O(1), as constant extra space is used.

GeeksforGeeks

Improve

Previous Article

Special two digit numbers in a Binary Search Tree

Similar Reads

Total number of possible Binary Search Trees and Binary Trees with n keys

Total number of possible Binary Search Trees with n different keys (countBST(n)) = Catalan number Cn = (2n)! / ((n + 1)! * n!) For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, .... So are numbers of Binary Search Trees. Total number of possible Binary Trees with n different keys (countBT(n)) = countBST(n

Data Structures | Balanced Binary Search Trees | Question 2

The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is (A) [Tex]\\Theta(n log n) [/Tex](B) [Tex]\\Theta (n2^n) [/Tex](C) [Tex]\\Theta (n) [/Tex](D) [Tex]\\Theta (log n) [/Tex] (A) A (B) B (C) C (D) D Answer: (C)Explanation: Time taken to search an element is [Tex]\\Theta (h) [/Tex]where h is

Data Structures | Balanced Binary Search Trees | Question 2

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0. (A) 2 (B) 3 (C) 4 (D) 5 Answer: (B) Explanation: AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees Following is the most unbalanced AVL tre

Data Structures | Balanced Binary Search Trees | Question 4

Which of the following is AVL Tree? A 100 / \ 50 200 / \ 10 300 B 100 / \ 50 200 / / \ 10 150 300 / 5 C 100 / \ 50 200 / \ / \ 10 60 150 300 / \ \ 5 180 400 (A) Only A (B) A and C (C) A, B and C (D) Only B Answer: (B) Explanation: A Binary Search Tree is AVL if balance factor of every node is either -1 or 0 or 1. Balance factor of a node X is [(hei

Data Structures | Balanced Binary Search Trees | Question 5

Consider the following AVL tree. 60 / \ 20 100 / \ 80 120 Which of the following is updated AVL tree after insertion of 70 A 70 / \ 60 100 / / \ 20 80 120 B 100 / \ 60 120 / \ / 20 70 80 C 80 / \ 60 100 / \ \ 20 70 120 D 80 / \ 60 100 / / \ 20 70 120 (A) A (B) B (C) C (D) D Answer: (C) Explanation: Refer following for steps used in AVL insertion. A

Data Structures | Balanced Binary Search Trees | Question 13

Which of the following is a self-adjusting or self-balancing Binary Search Tree (A) Splay Tree (B) AVL Tree (C) Red Black Tree (D) All of the above Answer: (D) Explanation: See Splay Tree, AVL Tree and Red Black TreeQuiz of this Question

Data Structures | Balanced Binary Search Trees | Question 7

Consider the following left-rotate and right-rotate functions commonly used in self-adjusting BSTs T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x (on right side) y x / \ Right Rotation / \ x T3 – - – - – - – > T1 y / \ < - - - - - - - / \ T1 T2 Left Rotation T2 T3 Which of the following is tightest upper bound for le

Data Structures | Balanced Binary Search Trees | Question 13

Which of the following is true (A) The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. (B) Heights of AVL and Red-Black trees are generally same, but AVL Trees may cause more rotations during insertion and deletion. (C) Red Black trees are more balanced compared to AVL Trees,

Data Structures | Balanced Binary Search Trees | Question 9

Which of the following is true about Red Black Trees? (A) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf (B) At least one children of every black node is red (C) Root may be red (D) A leaf node may be red Answer: (A) Explanation: See http://en.wikipedia.org/wiki/Red%E2%80%93bl

Data Structures | Balanced Binary Search Trees | Question 13

Which of the following is true about AVL and Red Black Trees? (A) In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node. (B) In both AVL and Red Black insert operations, we traverse only on

Data Structures | Balanced Binary Search Trees | Question 11

What is the worst case possible height of Red-Black tree? Assume base of Log as 2 in all options (A) 2Log(n+1) (B) 1.44 Logn (C) 4Logn (D) None of the above Answer: (A) Explanation: Refer Wiki Page of Red-Black TreeQuiz of this Question

Data Structures | Balanced Binary Search Trees | Question 12

Is the following statement valid? A Red-Black Tree which is also a perfect Binary Tree can have all black nodes (A) Yes (B) No Answer: (A) Explanation: A perfect BST with all black nodes doesn't violate any of the Red-Black tree properties.Quiz of this Question

Data Structures | Balanced Binary Search Trees | Question 13

Which of the following operations are used by Red-Black trees to maintain balance during insertion/deletion? a) Recoloring of nodes b) Rotation (Left and Right) (A) Only a (B) Only b (C) Both a and b (D) Neither a nor b Answer: (C) Explanation: Both recoloring and rotation operations are used during insertion and deletion.Quiz of this Question

Data Structures | Balanced Binary Search Trees | Question 10

What is the worst case possible height of AVL tree? (A) 2Logn (Assume base of log is 2) (B) 1.44log n (Assume base of log is 2) (C) Depends upon implementation (D) Theta(n) Answer: (B) Explanation: The worst-case height of an AVL tree is 1.44 log n, where n is the number of nodes in the tree. This height is achieved when the tree is perfectly balan

Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)

Given two binary trees. We need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of new tree. Example: Input: Tree 1 Tree 2 2 3 / \ / \ 1 4 6 1 / \ \ 5 2 7 Output: Merged tree: 5 / \ 7 5 / \ \ 5 2 7 No

Count Balanced Binary Trees of Height h

Given a height h, count and return the maximum number of balanced binary trees possible with height h. A balanced binary tree is one in which for every node, the difference between heights of left and right subtree is not more than 1. Examples : Input : h = 3 Output : 15 Input : h = 4 Output : 315Recommended PracticeBBT counterTry It! Following are

Comparison between Height Balanced Tree and Weight Balanced Tree

What is Height Balanced Tree? Self-Balancing binary search trees are the height-balanced binary tree is one for which at every node, the absolute value of the difference in heights of the left and right subtree is no larger than one. An empty tree is height-balanced. A non-empty binary tree T is balanced if: The left subtree of T is balanced.The ri

Count the Number of Binary Search Trees present in a Binary Tree

Given a binary tree, the task is to count the number of Binary Search Trees present in it. Examples: Input: 1 / \ 2 3 / \ / \ 4 5 6 7 Output: 4Here each leaf node represents a binary search tree and there are total 4 nodes. Input: 11 / \ 8 10 / / \ 5 9 8 / \ 4 6 Output: 6 Sub-tree rooted under node 5 is a BST 5 / \ 4 6 Another BST we have is rooted

Print Common Nodes in Two Binary Search Trees

Given two Binary Search Trees, find common nodes in them. In other words, find the intersection of two BSTs. Example: Input: root1: 5 / \ 1 10 / \ / 0 4 7 \ 9 root2: 10 / \ 7 20 / \4 9Output: 4 7 9 10 Recommended PracticeFind Common Nodes in two BSTsTry It! Naive Approach: A simple way is to one by one search every node of the first tree in the sec

Weak AVL or Rank Balanced Trees

Weak AVL trees, also known as rank-balanced trees, are a type of self-balancing binary search tree that aims to balance the tree while minimizing the number of rotations needed to maintain balance. These trees are similar to AVL trees in that they both use rotations to maintain balance, but they differ in how they define balance. Explanation: In an

Construct a Maximum Binary Tree from two given Binary Trees

Given two Binary Trees, the task is to create a Maximum Binary Tree from the two given binary trees and print the Inorder Traversal of that tree. What is the maximum Binary Tree? The maximum binary is constructed in the following manner: In the case of both the Binary Trees having two corresponding nodes, the maximum of the two values is considered

Sorting with Tapes : Balanced Merge

Balanced merge is a type of sorting algorithm where data is stored on multiple tapes (or other forms of storage). The tapes are divided into two groups: odd-numbered tapes and even-numbered tapes. The data on each tape is initially sorted, and the algorithm's goal is to merge the data from all of the tapes into a single sorted output. Approach: Her

Meta Binary Search | One-Sided Binary Search

Meta binary search (also called one-sided binary search by Steven Skiena in The Algorithm Design Manual on page 134) is a modified form of binary search that incrementally constructs the index of the target value in the array. Like normal binary search, meta binary search takes O(log n) time. Meta Binary Search, also known as One-Sided Binary Searc

Data Structures | Binary Search Trees | Question 1

What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree for a skewed tree ? (A) O(n) for all (B) O(Logn) for all (C) O(Logn) for search and insert, and O(n) for delete (D) O(Logn) for search, and O(n) for insert and delete Answer: (A)Explanation: In skewed Binary Search Tree (BST), all three o

Data Structures | Binary Search Trees | Question 2

In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation? (A) Inorder Successor is always a leaf node (B) Inorder successor is always either a leaf node or a node with empt

Data Structures | Binary Search Trees | Question 4

How many distinct binary search trees can be created out of 4 distinct keys? (A) 4 (B) 14 (C) 24 (D) 42 Answer: (B) Explanation: number of distinct BSTs = (2n)!/[(n+1)!*n!] . Quiz of this Question Please comment below if you find anything wrong in the above post

Data Structures | Binary Search Trees | Question 5

Which of the following traversal outputs the data in sorted order in a BST? (A) Preorder (B) Inorder (C) Postorder (D) Level order Answer: (B)Explanation: Inorder traversal of a BST outputs data in sorted order. Quiz of this QuestionPlease comment below if you find anything wrong in the above post

Data Structures | Binary Search Trees | Question 6

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree? (A) 7 5 1 0 3 2 4 6 8 9 (B) 0 2 4 3 1 6 5 9 8 7 (C) 0 1 2 3 4 5 6 7 8 9 (D) 9 8 6 4 2 3 0 1 5 7 Answ

Data Structures | Binary Search Trees | Question 7

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004) (A)2 (B)3 (C)4 (D)6 Answer: (B)Explanation: Constructed binary search tree will be. Quiz of this QuestionPleas

Data Structures | Binary Search Trees | Question 10

Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder (A) Any one of the given three traversals is sufficient (B) Either 2 or 3 is sufficient (C) 2 and 3 (D) 1 and 3 Answer: (B) Explanation: When we know either preorder or postorder traversal, we can construct the BST. Note that w

Article Tags :

Practice Tags :

Binary Search Tree