Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

&nbsp;
Example 1:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]


Example 2:

Input: root = [5,1,7]
Output: [1,null,5,null,7]


&nbsp;
Constraints:


	The number of nodes in the given tree will be in the range [1, 100].
	0 &lt;= Node.val &lt;= 1000


class Solution(object):
    
    def increasingBST(self, root):
        
        def sortBST(node):
            if not node:    return []
            
            # return the in order BST nodes in list
            return sortBST(node.left) + [node.val] + sortBST(node.right)
            
        # the in order sorted list of the tree nodes
        sorted_list = sortBST(root)
        
        # generate new tree: temp for update, ans for return the root
        ans = temp = TreeNode(sorted_list[0])
        
        # insert nodes to the right side of the new tree
        for i in range(1, len(sorted_list)):
            temp.right = TreeNode(sorted_list[i])
            temp = temp.right
            
        return ans
class Solution {
    TreeNode inRoot = new TreeNode();
    TreeNode temp = inRoot;
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        return inRoot.right;
    }
    public void inorder(TreeNode root) {
        if(root==null)
            return;
        inorder(root.left);
        temp.right = new TreeNode(root.val);
        temp = temp.right;
        inorder(root.right);
    }
}
/**
 * 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* temp;
    vector<int>z;
    TreeNode* increasingBST(TreeNode* root) 
    {  
        incresing(root);    
        sort(z.begin(), z.end());
        temp = new TreeNode(z[0]);
        create(temp, z);
        return temp;
    }
    void incresing(TreeNode* root)
    {
        if(root == NULL)  return;
        
        z.push_back(root->val);
        incresing(root->left);
        incresing(root->right);        
    }
    void create(TreeNode* create, vector<int> ze)
    {
          
        for(int i = 1; i<ze.size(); i++)
        {
            cout<<ze[i]<<endl;
            create->right = new TreeNode(ze[i]);
            create = create->right;
        }       
    }
};
var increasingBST = function(root) {
    let newRoot = new TreeNode(-1);
    const newTree = newRoot;

    const dfs = (node) => {
        if (!node) return null;

        if (node.left) dfs(node.left);

        const newNode = new TreeNode(node.val);
        newRoot.right = newNode;
        newRoot.left = null;
        newRoot = newRoot.right;

        if (node.right) dfs(node.right);
    }
    dfs(root);

    return newTree.right;
};
Increasing Order Search Tree