How to merge two binary search trees maintaining the property of BST?
If we decide to take each element from a tree and insert it into the other, the complexity of this method would be O(n1 * log(n2))
, where n1
is the number of nodes of the tree (say T1
), which we have splitted, and n2
is the number of nodes of the other tree (say T2
). After this operation only one BST has n1 + n2
nodes.
My question is: can we do any better than O(n1 * log(n2))?
Solution Steps Perform inorder traversal of tree1 and store each node's value in arr1. Perform inorder traversal of tree2 and store each node's value in arr2. Combine arr1 and arr2 using merge function of merge sort to create result array. Return result array.
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.
Naaff's answer with a little more details:
Three steps of O(n1+n2) result in O(n1+n2)
For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))
[1] Algorithm for creating a balanced BST from a sorted list (in Python):
def create_balanced_search_tree(iterator, n): if n == 0: return None n_left = n//2 n_right = n - 1 - n_left left = create_balanced_search_tree(iterator, n_left) node = iterator.next() right = create_balanced_search_tree(iterator, n_right) return {'left': left, 'node': node, 'right': right}
IIRC, that is O(n1+n2).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With