Understanding the Problem
We are given two binary search trees (BSTs), and our task is to merge them into a single balanced binary search tree.
A BST is a special kind of binary tree where the left subtree has smaller values than the root, and the right subtree has larger values.
Merging two BSTs involves collecting all their values, ensuring they are sorted, and then constructing a new BST that is height-balanced.
Step-by-Step Solution with Example
Step 1: In-order Traversal of Both Trees
Perform an in-order traversal on each of the two trees. In-order traversal visits nodes in sorted order (left, root, right).
So, for Tree1 = [2, 1, 4], in-order traversal gives [1, 2, 4].
For Tree2 = [3, 6], in-order traversal gives [3, 6].
Step 2: Merge the Two Sorted Arrays
Use a two-pointer merge technique, just like the merge step in merge sort, to combine the two sorted arrays into one sorted array.
From the previous step, we merge [1, 2, 4] and [3, 6] to get [1, 2, 3, 4, 6].
Step 3: Build a Balanced BST from Merged Array
Now that we have a sorted array [1, 2, 3, 4, 6], we construct a balanced BST by picking the middle element as the root (which ensures minimal height).
Then recursively build the left and right subtrees from the left and right halves of the array.
Step 4: Return the New BST
The constructed tree is a balanced BST that contains all the nodes from both input trees.
Edge Cases
Case 1: One Tree is Empty
If one of the trees is empty, we can skip traversal and merging for that tree.
The other tree is already a valid BST, so we return it directly.
Example: Tree1 = [] and Tree2 = [1] → Result: [1]
Case 2: Both Trees are Empty
If both trees are empty, the result is also an empty tree.
This is a base case handled easily by returning null
or an empty list.
Case 3: Trees with Disjoint or Overlapping Values
If the ranges of values in both trees do not overlap (e.g., all values in Tree1 < Tree2), the merged array will still be sorted.
If values overlap, the merge step maintains sorted order.
Example: Tree1 = [5, 3, 7, 2, 4, 6, 8], Tree2 = [10, 9, 11] → Merged: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Case 4: Skewed Trees
If input trees are skewed (all nodes on one side), they still produce sorted arrays during in-order traversal.
The final constructed BST will be balanced regardless of input tree shape.
Finally
This approach is intuitive and modular. It breaks down the problem into manageable parts: traversal, merge, and construction.
It also naturally handles edge cases like empty trees or skewed structures.
The key idea is transforming trees into sorted arrays and then back into a balanced BST, preserving the correctness and efficiency of BST operations.
Comments
Loading comments...