https://leetcode.com/problems/increasing-order-search-tree

Let us construct new tree, using already existing nodes. My dfs function will have two outputs: node with smallest value (root of tree) and node with biggest value (leaf of tree). Then, all we need to do is to run dfs recursively:

  1. First, we denote l1 = node and r2 = node, this is for the case, if we will not have left or right children.
  2. If we have left children, we create straight tree for left subtree using recursion and attach our node as right children of leaf of this tree.
  3. If we have right children, we againg create straigh tree for right subtree using recursion and attach r1 as right children of node.
  4. We put left children of node to None to avoid loops in our final tree.
  5. Return dfs(root)[0]: only root of constructed tree, not need to return leaf.

Complexity: time complexity is O(n), because we visit each node exactly once. Space compexity is O(h), height of our tree.

class Solution:
    def increasingBST(self, root):
        def dfs(node):
            l1, r2 = node, node
            
            if node.left: 
                l1, l2 = dfs(node.left)
                l2.right = node
                
            if node.right:
                r1, r2 = dfs(node.right)
                node.right = r1
            
            node.left = None
            return (l1, r2)
        
        return dfs(root)[0]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0897