Increasing Order Search Tree
The task is to rearrange the tree in inorder so that the leftmost node in the tree becomes the root of the tree, and every node has no left child and only one right child.
To do this, we can perform an inorder traversal of the binary search tree (BST) and link the nodes as we visit them.
Approach
 Initialize Pointers: Create a dummy node and a current pointer. Set the current pointer to the dummy node.
 InOrder Traversal: Perform an inorder traversal of the tree (leftrootright).
 Visit Left: Recursively traverse the left subtree.
 Visit Root: Set the right child of the current node to the root. Move the current pointer to its right child. Set the left child of the root to null.
 Visit Right: Recursively traverse the right subtree.
 Return Result: The new root of the tree will be the right child of the dummy node.
Code


Example
 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]
 Explanation: By inorder traversal, we link nodes as we visit them, resulting in the desired structure.
Insights
Time Complexity: The time complexity is (O(n)), where (n) is the number of nodes in the tree, as we visit each node exactly once.
Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree, since the inorder traversal uses recursive calls and consumes space on the call stack.
InPlace Modification: This solution modifies the original tree in place without creating new nodes, achieving a spaceefficient solution.
 Identify the traversal. Inorder traversal
 Keep all the values of the node in a list
 Traverse through the list and create the new tree
 Keep previous node 
 We need to traverse to the right
 What should be the left child? None
 What should be the right child?

