Merge BSTs to Create Single BST LeetCode solution in Python

1
# Runtime: 2457 ms (Top 91.30%) | Memory: 66.7 MB (Top 52.17%)
2
class Solution:
3
    def canMerge(self, trees: List[TreeNode]) -> TreeNode:
4
        n = len(trees)
5
        if n == 1:
6
            return trees[0]
7

8
        value_to_root = {}  # Map each integer root value to its node
9
        appeared_as_middle_child = (
10
            set()
11
        )  # All values appearing in trees but not in a curr or leaf
12
        self.saw_conflict = (
13
            False  # If this is ever true, break out of function and return None
14
        )
15
        leaf_value_to_parent_node = {}
16

17
        def is_leaf_node(curr: TreeNode) -> bool:
18
            return curr.left is None and curr.right is None
19

20
        def get_size(curr: TreeNode) -> int:  # DFS to count Binary Tree Size
21
            if curr is None:
22
                return 0
23
            return 1 + get_size(curr.left) + get_size(curr.right)
24

25
        def is_valid_bst(
26
            curr: TreeNode, lo=-math.inf, hi=math.inf
27
        ) -> bool:  # Standard BST validation code
28
            if curr is None:
29
                return True
30
            return all(
31
                (
32
                    lo < curr.val < hi,
33
                    is_valid_bst(curr.left, lo, curr.val),
34
                    is_valid_bst(curr.right, curr.val, hi),
35
                )
36
            )
37

38
        def process_child(child_node: TreeNode, parent: TreeNode) -> None:
39
            if child_node is None:
40
                return None
41
            elif (
42
                child_node.val in leaf_value_to_parent_node
43
                or child_node.val in appeared_as_middle_child
44
            ):
45
                self.saw_conflict = (
46
                    True  # Already saw this child node's value in a non-root node
47
                )
48
            elif is_leaf_node(child_node):
49
                leaf_value_to_parent_node[child_node.val] = parent
50
            elif child_node.val in value_to_root:
51
                self.saw_conflict = True
52
            else:
53
                appeared_as_middle_child.add(child_node.val)
54
                process_child(child_node.left, child_node)
55
                process_child(child_node.right, child_node)
56

57
        def process_root(curr_root: TreeNode) -> None:
58
            value_to_root[curr_root.val] = curr_root
59

60
            if curr_root.val in appeared_as_middle_child:
61
                self.saw_conflict = True
62
            else:
63
                process_child(curr_root.left, curr_root)
64
                process_child(curr_root.right, curr_root)
65

66
        for root_here in trees:
67
            process_root(root_here)
68
            if self.saw_conflict:
69
                return None
70

71
        final_expected_size = (
72
            len(leaf_value_to_parent_node) + len(appeared_as_middle_child) + 1
73
        )
74

75
        final_root = None  # The root of our final BST will be stored here
76
        while value_to_root:
77
            root_val, root_node_to_move = value_to_root.popitem()
78

79
            if root_val not in leaf_value_to_parent_node:  # Possibly found main root
80
                if final_root is None:
81
                    final_root = root_node_to_move
82
                else:
83
                    return None  # Found two main roots
84
            else:
85
                new_parent = leaf_value_to_parent_node.pop(root_val)
86
                if new_parent.left is not None and new_parent.left.val == root_val:
87
                    new_parent.left = root_node_to_move
88
                    continue
89
                elif new_parent.right is not None and new_parent.right.val == root_val:
90
                    new_parent.right = root_node_to_move
91
                else:
92
                    return None  # Didn't find a place to put this node
93

94
        # Didn't find any candidates for main root, or have a cycle, or didn't use all trees
95
        if (
96
            final_root is None
97
            or not is_valid_bst(final_root)
98
            or get_size(final_root) != final_expected_size
99
        ):
100
            return None
101

102
        return final_root