Merge two BST 's - POTD | 30-Sep-2024

[MuhammadTausif]

Merge two BST 's

Link

Difficulty: Medium

Given two BSTs, return elements of merged BSTs in sorted form.

Examples :

Input:
BST1:
       5
     /   \
    3     6
   / \
  2   4  
BST2:
        2
      /   \
     1     3
            \
             7
            /
           6
Output: 1 2 2 3 3 4 5 6 6 7
Explanation: After merging and sorting the two BST we get 1 2 2 3 3 4 5 6 6 7.
Input:
BST1:
       12
     /   
    9
   / \    
  6   11
BST2:
      8
    /  \
   5    10
  /
 2
Output: 2 5 6 8 9 10 11 12
Explanation: After merging and sorting the two BST we get 2 5 6 8 9 10 11 12.

*Expected Time Complexity: O((m+n)log(m+n)) Expected Auxiliary Space: O(Height of BST1 + Height of BST2 + m + n)**

Constraints:

• 1 ≤ Number of Nodes, value of nodes ≤ 10^5

[MuhammadTausif]

Solved

class Solution:
    def inorder(self,root):
        l=[]
        def helper(node):
            if node is None:
                return None
            helper(node.left)
            l.append(node.data)
            helper(node.right)
            return l
        return helper(root)
    def merge(self, root1, root2):
        final=self.inorder(root1)+self.inorder(root2)
        final.sort()
        return final