Scene 1

Merge Two Balanced Binary Search Trees   AVL or Red-Black Tree .

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

Scene 2

Did Inorder traversal of first tree and stored the traversal in one temp array arr1[].This step takes O(m) time. Did Inorder traversal of second tree and store the traversal in another temp array arr2[]. This step takes O(n) time.  arr1[] and arr2[] 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.

Scene 3

Get the Middle of the array and make it root.  Recursively do same for left half and right half. Get the middle of left half and make it left child of the root created in step 1.  Get the middle of right half and make it right child of troot created in step 1. This step takes O(m+n) time. This method takes O(m+n) time even if the input BSTs are not balanced. Following is implementation of this method.

Scene 4

Problems
@ Javadoc Declaration Console
< terminated> Mer esTw08aIanced8STsIntoA8aIanced8ST [Java A lication]
The output shows the
32 67 7B 3B
The output shows the
15 23 12
The output shows the
15 23 12 32 9ø 67 7ø
Inorder traversal of the AVLtreeI :
Inorder traversal of the R8tree2:
Inorder traversal of the merged 8ST:
3ø

Merge Two Balanced Binary Search Trees AVL or Red-Black Tree.

Scene 1 (0s)

Scene 2 (26s)

Scene 3 (49s)

Scene 4 (1m 12s)