LeetCode | Hard | 1932 Merge BSTs to Create Single BST | Python Solution

 

Approach

1. Indentify your root tree from where merging will being .
2. Now from remaining trees , apply helper function to merge.
3. If final tree is valid BST then return tree else return None.

Youtube Link : https://www.youtube.com/watch?v=3QC5L5W0Lhk

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    is_merged = False
    def canMerge(self, trees):
        """
        :type trees: List[TreeNode]
        :rtype: TreeNode
        """
        if len(trees) == 1:
            return trees[0]

        #Find List of Leaf Nodes
        all_leaves_node = set()
        for tree in trees :
            if tree.left :
                all_leaves_node.add(tree.left.val)
            if tree.right :
                all_leaves_node.add(tree.right.val)    

        # Find start point - root node for all other tress
        root = None 
        for tree in trees:
            if tree.val not in all_leaves_node:
                root = tree

        #If we do not find any root node.   
        if root is None :
             return None 

        
        # List of Remaining trees except root node tree
        list_of_remaining_tree = []
        for tree in trees :
            if tree.val != root.val :
                list_of_remaining_tree.append(tree)
        

        # Dictionary of root node value and tree
        root_tree_dictionary = {}
        for tree in list_of_remaining_tree:
             root_tree_dictionary[tree.val] = tree

        #Perform Merging of Tree
        self.helper(root,root_tree_dictionary)

        # Finally check if it is a valid BST 
        if self.check_valid_bst(root , float('-inf') , float('inf')) \
            and len(root_tree_dictionary) == 0:
                return root
        else:
            return None # If not a valid BST then return empty tree
       
             
    def helper(self, root , root_tree_dictionary):     
        if root is None :
            return None 

        #if root node is found in dictionary then peform merge 
        if root.val in root_tree_dictionary:
            tree = root_tree_dictionary[root.val]
            root.left = tree.left
            root.right = tree.right 
            root_tree_dictionary.pop(root.val)
                
        left = self.helper(root.left, root_tree_dictionary)
        right = self.helper(root.right, root_tree_dictionary)
    
    # Function for checking if it is a valid BST 
    def check_valid_bst(self,root, min_value , max_value) :
            return not root or min_value < root.val < max_value and \
                    self.check_valid_bst(root.left, min_value, root.val) and \
                    self.check_valid_bst(root.right, root.val, max_value)