In-place merge two height-balanced BSTs
Given two height-balanced binary search trees, in-place merge them into a single balanced binary search tree. For each node of a height-balanced tree, the difference between its left and right subtree height is at most 1.
For example,
Input: Below BSTs
20
/ \
10 30
/ \
25 100
50
/ \
5 70
Output:
30
/ \
20 70
/ \ / \
10 25 50 100
/
5
OR
25
/ \
10 50
/ \ / \
5 20 30 70
\
100
OR
Any other possible representation.
20
/ \
10 30
/ \
25 100
50
/ \
5 70
Output:
30
/ \
20 70
/ \ / \
10 25 50 100
/
5
OR
25
/ \
10 50
/ \ / \
5 20 30 70
\
100
OR
Any other possible representation.
A simple solution is to perform postorder traversal on the smaller tree and insert each encountered “node” into the larger BST. Insertion into a height-balanced BST of size n takes O(log(n)) time. Therefore, the overall time complexity of this approach will be O(m.log(n)) for m keys in the smaller BST and n keys in the larger BST. We can improve the time complexity by using any of the following methods:
1. Using Extra space
The idea is to perform the inorder traversal on both BSTs and store the traversals in two different arrays. These arrays would be in sorted order since the BST inorder traversal traverses the nodes in sorted order. Then merge the sorted arrays into a single array using logic similar to the merge routine of the merge sort algorithm. Finally, construct a height-balanced BST from the sorted keys using logic discussed in the following post.
Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
#include <iostream> #include <vector> using namespace std; // A BST node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to print preorder traversal of the BST void preorder(Node* root) { if (root == nullptr) { return; } cout << root->data << " "; preorder(root->left); preorder(root->right); } // Function to store inorder traversal of a BST in a given list void inorder(Node* root, vector<Node*> &nodes) { if (root == nullptr) { return; } inorder(root->left, nodes); nodes.push_back(root); inorder(root->right, nodes); } // Function to merge two sorted lists into a single sorted list vector<Node*> sortedMerge(vector<Node*> first, vector<Node*> second) { vector<Node*> result; int i = 0, j = 0; while (i < first.size() && j < second.size()) { // if the next node of the first list is smaller if (first[i]->data < second[j]->data) { result.push_back(first[i++]); } // if the next node of the second list is smaller else { result.push_back(second[j++]); } } // add any remaining nodes to the output list while (i < first.size()) { result.push_back(first[i++]); } while (j < second.size()) { result.push_back(second[j++]); } return result; } // Function to construct a balanced BST from a sorted list Node* toBalancedBST(vector<Node*> nodes, int low, int high) { // base case if (low > high) { return nullptr; } // find the middle of the current range int mid = (low + high) / 2; // `root` is the node corresponding to `mid` Node* root = nodes[mid]; // construct left subtree from nodes less than `mid` root->left = toBalancedBST(nodes, low, mid - 1); // construct the right subtree from nodes more than `mid` root->right = toBalancedBST(nodes, mid + 1, high); // return root node return root; } // Function to merge two balanced BSTs into a single balanced BST Node* merge(Node* a, Node* b) { // store inorder traversal of the first BST in a list vector<Node*> first; inorder(a, first); // store inorder traversal of the second BST in another list vector<Node*> second; inorder(b, second); // merge both lists into a new sorted list vector<Node*> sortedNodes = sortedMerge(first, second); // construct and return the balanced BST from the sorted list return toBalancedBST(sortedNodes, 0, sortedNodes.size() - 1); } int main() { /* Construct the first BST 20 / \ 10 30 / \ 25 100 */ Node* first = new Node(20); first->left = new Node(10); first->right = new Node(30); first->right->left = new Node(25); first->right->right = new Node(100); /* Construct the second BST 50 / \ 5 70 */ Node* second = new Node(50); second->left = new Node(5); second->right = new Node(70); // merge both BSTs Node* root = merge(first, second); preorder(root); return 0; } |
Output:
25 10 5 20 50 30 70 100
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
import java.util.ArrayList; import java.util.List; // A BST node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Function to print preorder traversal of the BST public static void preorder(Node root) { if (root == null) { return; } System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } // Function to store inorder traversal of a BST in a given list public static void inorder(Node root, List<Node> nodes) { if (root == null || nodes == null) { return; } inorder(root.left, nodes); nodes.add(root); inorder(root.right, nodes); } // Function to merge two sorted lists into a single sorted list public static List<Node> sortedMerge(List<Node> first, List<Node> second) { List<Node> result = new ArrayList<>(); int i = 0, j = 0; while (i < first.size() && j < second.size()) { // if the next node of the first list is smaller if (first.get(i).data < second.get(j).data) { result.add(first.get(i++)); } // if the next node of the second list is smaller else { result.add(second.get(j++)); } } // add any remaining nodes to the output list while (i < first.size()) { result.add(first.get(i++)); } while (j < second.size()) { result.add(second.get(j++)); } return result; } // Function to construct a balanced BST from a sorted list public static Node toBalancedBST(List<Node> nodes, int low, int high) { // base case if (low > high) { return null; } // find the middle of the current range int mid = (low + high) / 2; // `root` is the node corresponding to `mid` Node root = nodes.get(mid); // construct left subtree from nodes less than `mid` root.left = toBalancedBST(nodes, low, mid - 1); // construct the right subtree from nodes more than `mid` root.right = toBalancedBST(nodes, mid + 1, high); // return root node return root; } // Function to merge two balanced BSTs into a single balanced BST public static Node merge(Node a, Node b) { // store inorder traversal of the first BST in a list List<Node> first = new ArrayList<>(); inorder(a, first); // store inorder traversal of the second BST in another list List<Node> second = new ArrayList<>(); inorder(b, second); // merge both lists into a new sorted list List<Node> sortedNodes = sortedMerge(first, second); // construct and return the balanced BST from the sorted list return toBalancedBST(sortedNodes, 0, sortedNodes.size() - 1); } public static void main(String[] args) { /* Construct the first BST 20 / \ 10 30 / \ 25 100 */ Node first = new Node(20); first.left = new Node(10); first.right = new Node(30); first.right.left = new Node(25); first.right.right = new Node(100); /* Construct the second BST 50 / \ 5 70 */ Node second = new Node(50); second.left = new Node(5); second.right = new Node(70); // merge both BSTs Node root = merge(first, second); preorder(root); } } |
Output:
25 10 5 20 50 30 70 100
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
# A BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def __repr__(self): return str(self.data) # Function to print preorder traversal of the BST def preorder(root): if root is None: return print(root.data, end=' ') preorder(root.left) preorder(root.right) # Function to store inorder traversal of a BST in a given list def inorder(root, nodes): if root is None: return inorder(root.left, nodes) nodes.append(root) inorder(root.right, nodes) # Function to merge two sorted lists into a single sorted list def sortedMerge(first, second): result = [] i = j = 0 while i < len(first) and j < len(second): # if the next node of the first list is smaller if first[i].data < second[j].data: result.append(first[i]) i = i + 1 # if the next node of the second list is smaller else: result.append(second[j]) j = j + 1 # add any remaining nodes to the output list while i < len(first): result.append(first[i]) i = i + 1 while j < len(second): result.append(second[j]) j = j + 1 return result # Function to construct a balanced BST from a sorted list def toBalancedBST(nodes, low, high): if low > high: # base case return None # find the middle of the current range mid = (low + high) // 2 # `root` is the node corresponding to `mid` root = nodes[mid] # construct left subtree from nodes less than `mid` root.left = toBalancedBST(nodes, low, mid - 1) # construct the right subtree from nodes more than `mid` root.right = toBalancedBST(nodes, mid + 1, high) # return root node return root # Function to merge two balanced BSTs into a single balanced BST def merge(a, b): # store inorder traversal of the first BST in a list first = [] inorder(a, first) # store inorder traversal of the second BST in another list second = [] inorder(b, second) # merge both lists into a new sorted list sortedNodes = sortedMerge(first, second) # construct and return the balanced BST from the sorted list return toBalancedBST(sortedNodes, 0, len(sortedNodes) - 1) if __name__ == '__main__': ''' Construct the first BST 20 / \ 10 30 / \ 25 100 ''' first = Node(20) first.left = Node(10) first.right = Node(30) first.right.left = Node(25) first.right.right = Node(100) ''' Construct the second BST 50 / \ 5 70 ''' second = Node(50) second.left = Node(5) second.right = Node(70) # merge both BSTs root = merge(first, second) preorder(root) |
Output:
25 10 5 20 50 30 70 100
The time complexity of the above solution is O(m + n), where m is the total number of nodes in the first BST and n is the total number of nodes in the second BST. The additional space used by the program is O(m + n).
2. In-Place Solution
The above solution is simple and works in linear time but uses extra space for storing the inorder traversals. This problem can be solved in-place without using the extra space. The idea is to convert both binary search trees into a sorted doubly linked list and then merge both lists into a single, doubly linked list. Finally, construct a height-balanced BST from the sorted doubly linked list. Refer to the above posts for implementation details.
- Merge two BSTs into a doubly-linked list in sorted order.
- Construct a height-balanced BST from a sorted doubly linked list.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 |
#include <iostream> using namespace std; // A BST node struct Node { int data; Node* left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to push a BST node at the front of a doubly-linked list Node* push(Node* root, Node* head) { root->right = head; if (head != nullptr) { head->left = root; } head = root; return head; } // Function to count the total number of nodes in a doubly-linked list int size(Node* node) { int counter = 0; while (node) { counter++; node = node->right; } return counter; } // Function to print preorder traversal of the BST void preorder(Node* root) { if (root == nullptr) { return; } cout << root->data << " "; preorder(root->left); preorder(root->right); } // Recursive function to construct a balanced BST from a sorted doubly-linked list Node* convertSortedDLLToBalancedBST(Node* &headRef, int n) { // base case if (n <= 0) { return nullptr; } // recursively convert the left subtree Node* leftSubTree = convertSortedDLLToBalancedBST(headRef, n/2); // `headRef` now points to the middle node of the sorted list // make the middle node of the sorted list the root node of the BST Node* root = headRef; // update left child of the root node root->left = leftSubTree; // update the head reference of the doubly linked list headRef = headRef->right; // recursively convert the right subtree with the remaining nodes root->right = convertSortedDLLToBalancedBST(headRef, n - (n/2 + 1)); /* +1 for the root node */ // return the root node return root; } /* Recursive function to convert a BST into a doubly-linked list `root` ——> Pointer to the root node of the BST `head` ——> Pointer to the head node of the doubly linked list */ Node* convertBSTtoSortedDLL(Node* root, Node* head) { // base case if (root == nullptr) { return head; } // recursively convert the right subtree head = convertBSTtoSortedDLL(root->right, head); // push the current node at the front of the doubly linked list head = push(root, head); // recursively convert the left subtree head = convertBSTtoSortedDLL(root->left, head); return head; } // Recursive function to merge two doubly-linked lists into a // single doubly linked list in sorted order Node* sortedMerge(Node* first, Node* second) { // if the first list is empty, return the second list if (first == nullptr) { return second; } // if the second list is empty, return the first list if (second == nullptr) { return first; } // if the head node of the first list is smaller if (first->data < second->data) { first->right = sortedMerge(first->right, second); first->right->left = first; return first; } // if the head node of the second list is smaller else { second->right = sortedMerge(first, second->right); second->right->left = second; return second; } } // Function to merge two balanced BSTs into a single balanced BST Node* merge(Node* first, Node* second) { // merge both BSTs into a sorted doubly linked list Node* head = sortedMerge(convertBSTtoSortedDLL(first, nullptr), convertBSTtoSortedDLL(second, nullptr)); // construct a balanced BST from a sorted doubly linked list return convertSortedDLLToBalancedBST(head, size(head)); } int main() { /* Construct the following BST 20 / \ 10 30 / \ 25 100 */ Node* first = new Node(20); first->left = new Node(10); first->right = new Node(30); first->right->left = new Node(25); first->right->right = new Node(100); /* Construct the following BST 50 / \ 5 70 */ Node* second = new Node(50); second->left = new Node(5); second->right = new Node(70); // merge both BSTs Node* root = merge(first, second); preorder(root); return 0; } |
Output:
30 20 10 5 25 70 50 100
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
// A BST node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } // Wrapper over `Node` class class NodeWrapper { public Node node; NodeWrapper(Node node) { this.node = node; } } class Main { // Method to push a BST node at the front of a doubly linked list public static Node push(Node root, Node head) { root.right = head; if (head != null) { head.left = root; } head = root; return head; } // Method to count the total number of nodes in a doubly-linked list public static int size(Node node) { int counter = 0; while (node != null) { node = node.right; counter++; } return counter; } // Method to print preorder traversal of the BST public static void preorder(Node root) { if (root == null) { return; } System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } // Recursive method to construct a balanced BST from a sorted doubly linked list public static Node convertSortedDLLToBalancedBST(NodeWrapper head, int n) { // base case if (n <= 0) { return null; } // recursively construct the left subtree Node leftSubTree = convertSortedDLLToBalancedBST(head, n/2); // `head` now points to the middle node of the sorted DDL // make the middle node of the sorted DDL as the root node of the BST Node root = head.node; // update left child of the root node root.left = leftSubTree; // update the head reference of the doubly linked list head.node = head.node.right; // recursively construct the right subtree with the remaining nodes root.right = convertSortedDLLToBalancedBST(head, n - (n/2 + 1)); /* +1 for the root Node */ // return the root node return root; } // Recursive method to convert a BST into a doubly-linked list. It takes // the BST's root node and the head node of the doubly linked list as an argument public static Node convertBSTtoSortedDLL(Node root, Node head) { // base case if (root == null) { return head; } // recursively convert the right subtree head = convertBSTtoSortedDLL(root.right, head); // push the current node at the front of the doubly linked list head = push(root, head); // recursively convert the left subtree head = convertBSTtoSortedDLL(root.left, head); return head; } // Recursive method to merge two doubly-linked lists into a // single doubly linked list in sorted order public static Node sortedMerge(Node first, Node second) { // if the first list is empty, return the second list if (first == null) { return second; } // if the second list is empty, return the first list if (second == null) { return first; } // if the head node of the first list is smaller if (first.data < second.data) { first.right = sortedMerge(first.right, second); first.right.left = first; return first; } // if the head node of the second list is smaller else { second.right = sortedMerge(first, second.right); second.right.left = second; return second; } } // Method to merge two balanced BSTs into a single balanced BST public static Node merge(Node first, Node second) { // merge both BSTs into a sorted doubly linked list Node head = sortedMerge(convertBSTtoSortedDLL(first, null), convertBSTtoSortedDLL(second, null)); // construct a balanced BST from a sorted doubly linked list // Wrap the `head` node, so its reference can be changed inside the function return convertSortedDLLToBalancedBST(new NodeWrapper(head), size(head)); } public static void main(String[] args) { /* Construct the first BST 20 / \ 10 30 / \ 25 100 */ Node first = new Node(20); first.left = new Node(10); first.right = new Node(30); first.right.left = new Node(25); first.right.right = new Node(100); /* Construct the second BST 50 / \ 5 70 */ Node second = new Node(50); second.left = new Node(5); second.right = new Node(70); // merge both BSTs Node root = merge(first, second); preorder(root); } } |
Output:
30 20 10 5 25 70 50 100
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
# A BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to push a BST node at the front of a doubly linked list def push(root, head): root.right = head if head: head.left = root head = root return head # Function to print and count the total number of nodes in a doubly-linked list def size(node): counter = 0 while node: node = node.right counter = counter + 1 return counter # Function to print preorder traversal of the BST def preorder(root): if root is None: return print(root.data, end=' ') preorder(root.left) preorder(root.right) # Recursive method to construct a balanced BST from a sorted doubly linked list def convertSortedDLLToBalancedBST(head, n): # base case if n <= 0: return None, head # recursively construct the left subtree leftSubTree, head = convertSortedDLLToBalancedBST(head, n // 2) # `head` now points to the middle node of the sorted DDL # make the middle node of the sorted DDL as the root node of the BST root = head # update left child of the root node root.left = leftSubTree # update the head reference of the doubly linked list head = head.right # recursively construct the right subtree with the remaining nodes root.right, head = convertSortedDLLToBalancedBST(head, n - (n // 2 + 1)) # +1 for the root # return the root node return root, head # Recursive method to convert a BST into a doubly-linked list. It takes # the BST's root node and the head node of the doubly linked list as an argument def convertBSTtoSortedDLL(root, head=None): # base case if root is None: return head # recursively convert the right subtree head = convertBSTtoSortedDLL(root.right, head) # push the current node at the front of the doubly linked list head = push(root, head) # recursively convert the left subtree head = convertBSTtoSortedDLL(root.left, head) return head # Recursive method to merge two doubly-linked lists into a # single doubly linked list in sorted order def sortedMerge(first, second): # if the first list is empty, return the second list if first is None: return second # if the second list is empty, return the first list if second is None: return first # if the head node of the first list is smaller if first.data < second.data: first.right = sortedMerge(first.right, second) first.right.left = first return first # if the head node of the second list is smaller else: second.right = sortedMerge(first, second.right) second.right.left = second return second # Function to merge two balanced BSTs into a single balanced BST def merge(first, second): # merge both BSTs into a sorted doubly linked list head = sortedMerge(convertBSTtoSortedDLL(first), convertBSTtoSortedDLL(second)) # construct a balanced BST from a sorted doubly linked list root, head = convertSortedDLLToBalancedBST(head, size(head)) return root if __name__ == '__main__': ''' Construct the first BST 20 / \ 10 30 / \ 25 100 ''' first = Node(20) first.left = Node(10) first.right = Node(30) first.right.left = Node(25) first.right.right = Node(100) ''' Construct the second BST 50 / \ 5 70 ''' second = Node(50) second.left = Node(5) second.right = Node(70) # merge both BSTs root = merge(first, second) preorder(root) |
Output:
30 20 10 5 25 70 50 100
The time complexity of the above solution is O(m + n), where m is the total number of nodes in the first BST and n is the total number of nodes in the second BST. The conversion is done in-place. However, since recursion is involved, the space used by the call stack is O(x + y), where x is the height of the first tree, and y is the height of the second tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)