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


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


Return the root of the resulting BST if it is possible to form a valid BST after performing n - 1 operations, or null if it is impossible to create a valid BST.

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


	Every node in the node's left subtree has a value&nbsp;strictly less&nbsp;than the node's value.
	Every node in the node's right subtree has a value&nbsp;strictly greater&nbsp;than the node's value.


A leaf is a node that has no children.

&nbsp;
Example 1:

Input: trees = [[2,1],[3,2,5],[5,4]]
Output: [3,2,5,1,null,4]
Explanation:
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]].

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]].

The resulting tree, shown above, is a valid BST, so return its root.

Example 2:

Input: trees = [[5,3,8],[3,2,6]]
Output: []
Explanation:
Pick i=0 and j=1 and merge trees[1] into trees[0].
Delete trees[1], so trees = [[5,3,8,2,6]].

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.


Example 3:

Input: trees = [[5,4],[3]]
Output: []
Explanation: It is impossible to perform any operations.


&nbsp;
Constraints:


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


class Solution:
    def canMerge(self, trees: List[TreeNode]) -> TreeNode:
        n = len(trees)
        if n == 1: return trees[0]

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

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

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

        def is_valid_bst(curr: TreeNode, lo=-math.inf, hi=math.inf) -> bool: # Standard BST validation code
            if curr is None: return True
            return all((lo < curr.val < hi,
                        is_valid_bst(curr.left, lo, curr.val),
                        is_valid_bst(curr.right, curr.val, hi)))

        def process_child(child_node: TreeNode, parent: TreeNode) -> None:
            if child_node is None:
                return None
            elif child_node.val in leaf_value_to_parent_node or child_node.val in appeared_as_middle_child:
                self.saw_conflict = True # Already saw this child node's value in a non-root node
            elif is_leaf_node(child_node):
                leaf_value_to_parent_node[child_node.val] = parent
            elif child_node.val in value_to_root:
                self.saw_conflict = True
            else:
                appeared_as_middle_child.add(child_node.val)
                process_child(child_node.left, child_node)
                process_child(child_node.right, child_node)

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

            if curr_root.val in appeared_as_middle_child:
                self.saw_conflict = True
            else:
                process_child(curr_root.left, curr_root)
                process_child(curr_root.right, curr_root)

        for root_here in trees:
            process_root(root_here)
            if self.saw_conflict: return None

        final_expected_size = len(leaf_value_to_parent_node) + len(appeared_as_middle_child) + 1

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

            if root_val not in leaf_value_to_parent_node: # Possibly found main root
                if final_root is None:
                    final_root = root_node_to_move
                else:
                    return None # Found two main roots
            else:
                new_parent = leaf_value_to_parent_node.pop(root_val)
                if new_parent.left is not None and new_parent.left.val == root_val:
                    new_parent.left = root_node_to_move
                    continue
                elif new_parent.right is not None and new_parent.right.val == root_val:
                    new_parent.right = root_node_to_move
                else:
                    return None # Didn't find a place to put this node

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

        return final_root
class Solution {
    public TreeNode canMerge(List<TreeNode> trees) {
        //Map root value to tree
        HashMap<Integer, TreeNode> map = new HashMap<>();
        for(TreeNode t : trees){
            map.put(t.val, t);
        }

        // Merge trees
        for(TreeNode t : trees){
            if(map.containsKey(t.val)){
                merger(t, map);
            }
        }

        //After merging we should have only one tree left else return null
        if(map.size() != 1) return null;
        else {
            //Return the one tree left after merging
            for(int c : map.keySet()) {
                //Check if final tree is valid else return null
                if(isValidBST(map.get(c))){
                    return map.get(c);
                } else return null;
            }
        }

      return null;

    }

    void merger(TreeNode t, HashMap<Integer, TreeNode> map){
        map.remove(t.val); // Remove current tree to prevent cyclical merging For. 2->3(Right) and 3->2(Left)
        //Merge on left
        if(t.left != null && map.containsKey(t.left.val) ){
            // Before merging child node, merge the grandchild nodes
            merger(map.get(t.left.val), map);
            t.left = map.get(t.left.val);
            map.remove(t.left.val);
        }

        // Merge on right
        if(t.right!=null && map.containsKey(t.right.val) ){
            // Before merging child node, merge the grandchild nodes
            merger(map.get(t.right.val), map);
            t.right = map.get(t.right.val);
            map.remove(t.right.val);
        }
        // Add tree back to map once right and left merge is complete
        map.put(t.val, t);
    }

    // Validate BST
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean helper(TreeNode root, long min, long max){
        if(root == null) return true;
        if(root.val <= min || root.val >= max) return false;
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* canMerge(vector<TreeNode*>& trees) {
        //store the leaves of every node

        unordered_map<int,TreeNode*> mp;
        
        //store the current min and current max nodes in the current tree
        unordered_map<TreeNode*,pair<int,int>> mini;
        for(int i=0;i<trees.size();i++)
        {
            pair<int,int> ans={trees[i]->val,trees[i]->val};
            if(trees[i]->left)
            {
                
                mp[trees[i]->left->val]={trees[i]};
                ans.first=trees[i]->left->val;
            }
            if(trees[i]->right)
            {
                mp[trees[i]->right->val]=trees[i];
                ans.second=trees[i]->right->val;
            }
            mini[trees[i]]=ans;
        }
        
        //store the number of merging operations we will be doing
        int count=0;
        int rootCount=0;
        TreeNode* root=NULL;
        //now for every node get the root
        for(int i=0;i<trees.size();i++)
        {
            
            //if the current tree can be merged into some other tree
            if(mp.find(trees[i]->val)!=mp.end())
            {
                count++;
                //merge them
                TreeNode* parent=mp[trees[i]->val];
                if(trees[i]->val < parent->val)
                {
                    //left child 
                    
                    //if the maximum of the current sub tree is greater than the parent value 
                    //then return NULL
                    if(parent->val <= mini[trees[i]].second)
                        return NULL;
                    //change the minimum value of the parent tree to the current min value of the tree
                    mini[parent].first=mini[trees[i]].first;
                    //merge the trees
                    parent->left=trees[i];
                }
                else  if(trees[i]->val > parent->val)
                {
                    //right child
                    
                    //if the minimum of the current tree is lesser than the parent value
                    //we cannot merge 
                    //so return NULL
                    if(parent->val >= mini[trees[i]].first)
                        return NULL;
                    
                    //change the parent tree maximum to the current tree maximum
                    mini[parent].second=mini[trees[i]].second;
                    //merge the trees
                    parent->right=trees[i];
                }
                //erase the current tree value
                mp.erase(trees[i]->val);
            }
            else{
                //it has no other tree to merge 
                //it is the root node we should return 
                if(rootCount==1)
                    return NULL;
                else 
                {
                    rootCount++;
                    root=trees[i];
                }
            }
        }
        //if we are not able to merge all trees return NULL
        if(count!=trees.size()-1)
            return NULL;
        return root;
        
    }
};
var canMerge = function(trees) {
    let Node={},indeg={}
    // traverse the mini trees and put back pointers to their parents, also figure out the indegree of each node
    let dfs=(node,leftparent=null,rightparent=null)=>{
        if(!node)return
        indeg[node.val]=indeg[node.val]||Number(leftparent!==null||rightparent!==null)
        node.lp=leftparent,node.rp=rightparent
        dfs(node.left,node,null),dfs(node.right,null,node)
    }
    for(let root of trees)
        Node[root.val]=root,
        dfs(root)
    //there are a lot of potential roots=> no bueno
    if(Object.values(indeg).reduce((a,b)=>a+b)!=Object.keys(indeg).length-1)
        return null
    //find THE root
    let bigRoot,timesMerged=0
    for(let root of trees)
        if(indeg[root.val]===0)
            bigRoot=root
    // traverse the tree while replacing each leaf that can be replaced
    let rec=(node=bigRoot)=>{
        if(!node)
            return
        if(!node.left&&!node.right){
            let toadd=Node[node.val]
            Node[node.val]=undefined //invalidating the trees you already used
            if(toadd===undefined)
                return
            //make the change
            if(node.lp===null&&node.rp===null)
                return
            else if(node.lp!==null)
                node.lp.left=toadd
            else
                node.rp.right=toadd
            timesMerged++
            rec(toadd)
        }
        else
            rec(node.left),rec(node.right)
    }
    rec()
    var isValidBST = function(node,l=-Infinity,r=Infinity) { //l and r are the limits node.val should be within
        if(!node)
            return true
        if(node.val<l || node.val >r)
            return false
        return isValidBST(node.left,l,node.val-1)&&isValidBST(node.right,node.val+1,r)
    };
    //check if every item was used and if the result bst is valid 
    return !isValidBST(bigRoot)||timesMerged!==trees.length-1?null:bigRoot
};
Merge BSTs to Create Single BST