<p>You are given <code>n</code> <strong>BST (binary search tree) root nodes</strong> for <code>n</code> separate BSTs stored in an array <code>trees</code> (<strong>0-indexed</strong>). Each BST in <code>trees</code> has <strong>at most 3 nodes</strong>, and no two roots have the same value. In one operation, you can:</p>

<ul>
	<li>Select two <strong>distinct</strong> indices <code>i</code> and <code>j</code> such that the value stored at one of the <strong>leaves </strong>of <code>trees[i]</code> is equal to the <strong>root value</strong> of <code>trees[j]</code>.</li>
	<li>Replace the leaf node in <code>trees[i]</code> with <code>trees[j]</code>.</li>
	<li>Remove <code>trees[j]</code> from <code>trees</code>.</li>
</ul>

<p>Return<em> the <strong>root</strong> of the resulting BST if it is possible to form a valid BST after performing </em><code>n - 1</code><em> operations, or</em><em> </em><code>null</code> <i>if it is impossible to create a valid BST</i>.</p>

<p>A BST (binary search tree) is a binary tree where each node satisfies the following property:</p>

<ul>
	<li>Every node in the node&#39;s left subtree has a value&nbsp;<strong>strictly less</strong>&nbsp;than the node&#39;s value.</li>
	<li>Every node in the node&#39;s right subtree has a value&nbsp;<strong>strictly greater</strong>&nbsp;than the node&#39;s value.</li>
</ul>

<p>A leaf is a node that has no children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d1.png" style="width: 450px; height: 163px;" />
<pre>
<strong>Input:</strong> trees = [[2,1],[3,2,5],[5,4]]
<strong>Output:</strong> [3,2,5,1,null,4]
<strong>Explanation:</strong>
In the first operation, pick i=1 and j=0, and merge trees[0] into trees[1].
Delete trees[0], so trees = [[3,2,5,1],[5,4]].
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram.png" style="width: 450px; height: 181px;" />
In the second operation, pick i=0 and j=1, and merge trees[1] into trees[0].
Delete trees[1], so trees = [[3,2,5,1,null,4]].
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram-2.png" style="width: 220px; height: 165px;" />
The resulting tree, shown above, is a valid BST, so return its root.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d2.png" style="width: 450px; height: 171px;" />
<pre>
<strong>Input:</strong> trees = [[5,3,8],[3,2,6]]
<strong>Output:</strong> []
<strong>Explanation:</strong>
Pick i=0 and j=1 and merge trees[1] into trees[0].
Delete trees[1], so trees = [[5,3,8,2,6]].
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram-3.png" style="width: 240px; height: 196px;" />
The resulting tree is shown above. This is the only valid operation that can be performed, but the resulting tree is not a valid BST, so return null.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d3.png" style="width: 430px; height: 168px;" />
<pre>
<strong>Input:</strong> trees = [[5,4],[3]]
<strong>Output:</strong> []
<strong>Explanation:</strong> It is impossible to perform any operations.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == trees.length</code></li>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li>The number of nodes in each tree is in the range <code>[1, 3]</code>.</li>
	<li>Each node in the input may have children but no grandchildren.</li>
	<li>No two roots of <code>trees</code> have the same value.</li>
	<li>All the trees in the input are <strong>valid BSTs</strong>.</li>
	<li><code>1 &lt;= TreeNode.val &lt;= 5 * 10<sup>4</sup></code>.</li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

"""
Main Idea: BST inorder traversal

How to find the root of the resulted BST?
    
    The root.val shall not appear as leaf in any other trees
    There shall be only one such root.val
    
    We could also use indegree to look at the problem: the indegree
    of the resulted BST root.val shall be 0. And there shall only be
    one such root value.


To do the traversal, we need to replace each leaf node with value equal to
that of the root of another tree in the given BST list. For this purpose, we could build a tree_root_val:tree map for conveniene of traversal.


As for traversal, we could use BSF, DFS as we like.

"""

class Solution:
    def canMerge(self, trees: List[TreeNode]) -> TreeNode:
        
        
        leaf_values = set()
        root_by_value = dict()
        for node in trees:
            # add to leaf_values set
            if node.left:
                leaf_values.add(node.left.val)
            if node.right:
                leaf_values.add(node.right.val)
            # add to root_by_value dict
            root_by_value[node.val] = node
            
        # find the possible resulting BST root
        root = None
        for node in trees:
            if node.val not in leaf_values:
                if root is None:
                    root = node
                else:
                    return None
                
        # prepare to do traversal
        if root is None:
            return None
        
        del root_by_value[root.val]

        # BFS
        queue = collections.deque([(root, float("-inf"), float("inf"))])
        while queue:
            node, low, high = queue.popleft()
            if not (low < node.val < high):
                return None
            if node.left:
                if node.left.val in root_by_value:
                    node.left = root_by_value[node.left.val]
                    del root_by_value[node.left.val]
                queue.append((node.left, low, node.val))
            if node.right:
                if node.right.val in root_by_value:
                    node.right = root_by_value[node.right.val]
                    del root_by_value[node.right.val]
                queue.append((node.right, node.val, high))
                
        
        return root if not root_by_value else None
    
    
class SolutionV2:
    def canMerge(self, trees: List[TreeNode]) -> TreeNode:
        
        
        leaf_values = set()
        root_by_value = dict()
        for node in trees:
            # add to leaf_values set
            if node.left:
                leaf_values.add(node.left.val)
            if node.right:
                leaf_values.add(node.right.val)
            # add to root_by_value dict
            root_by_value[node.val] = node
            
        # find the possible resulting BST root
        root = None
        for node in trees:
            if node.val not in leaf_values:
                if root is None:
                    root = node
                else:
                    return None
                
        # prepare to do traversal
        if root is None:
            return None
        
        del root_by_value[root.val]
        
        
        stack = []
        node = root
        low = float("-inf")
        high = float("inf")
        while stack or node is not None:
            while node is not None:
                if not (low < node.val < high):
                    return None
                stack.append((node, low, high))
                if node.left:
                    if node.left.val in root_by_value:
                        node.left = root_by_value[node.left.val]
                        del root_by_value[node.left.val]
                node = node.left
                # low, high = low, node.val
            node, low, high = stack.pop()
            if node.right:
                if node.right.val in root_by_value:
                    node.right =  root_by_value[node.right.val]
                node = node.right
                low, high = node.val, high
                
                
                
        return root if not root_by_value else None
            
            
        
            
                    

                
                    
                    
                    
        
            
        
        
1277