Increasing Order Search Tree

Difficulty: Easy | Acceptance: 79.00% | Paid: No Topics: Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree

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.

• Examples
• Constraints
• Approach 1: Recursive In-order Traversal with List
• Approach 2: Recursive In-order Relinking
• Approach 3: Iterative In-order Relinking

Examples

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]

Constraints

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

Approach 1: Recursive In-order Traversal with List

Intuition Perform a standard in-order traversal to collect all node values into a list, then iterate through that list to construct a new tree where each node only has a right child.

Steps

• Define an empty list to store values.
• Perform recursive in-order traversal (Left -> Root -> Right) to populate the list with values in sorted order.
• Create a dummy node to act as the starting point.
• Iterate through the sorted list, creating a new TreeNode for each value and linking it to the previous node’s right pointer.
• Return the dummy node’s right child as the new root.

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        vals = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)
        
        inorder(root)
        
        dummy = TreeNode(0)
        curr = dummy
        for v in vals:
            curr.right = TreeNode(v)
            curr = curr.right
            
        return dummy.right

Complexity

• Time: O(N) where N is the number of nodes, as we visit each node twice (once for traversal, once for construction).
• Space: O(N) to store the list of values and the recursion stack.
• Notes: Simple to implement but uses extra space proportional to the number of nodes.

Approach 2: Recursive In-order Relinking

Intuition Instead of storing values in a separate list, rearrange the tree nodes themselves during the in-order traversal. We maintain a prev pointer to keep track of the last node processed and link it to the current node.

Steps

• Initialize a dummy node and a prev pointer pointing to the dummy.
• Perform in-order traversal recursively.
• When visiting a node:
  • Sever its left child (set to null).
  • Link the prev node’s right child to the current node.
  • Update prev to the current node.
• Recursively process the right subtree.
• Return the dummy node’s right child.

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        dummy = TreeNode(0)
        self.prev = dummy
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            
            node.left = None
            self.prev.right = node
            self.prev = node
            
            inorder(node.right)
            
        inorder(root)
        return dummy.right

Complexity

• Time: O(N) as we visit each node exactly once.
• Space: O(H) for the recursion stack, where H is the height of the tree.
• Notes: More space-efficient than the list approach as it modifies the tree in-place without extra storage for values.

Approach 3: Iterative In-order Relinking

Intuition Convert the recursive relinking approach into an iterative one using a stack. This avoids potential stack overflow issues on very deep trees and follows the standard iterative in-order traversal pattern.

Steps

• Initialize a dummy node and a curr pointer.
• Use a stack to simulate the recursion.
• While the stack is not empty or the current node is not null:
  • Push all left children onto the stack.
  • Pop a node from the stack.
  • Set its left child to null.
  • Link curr.right to this node and advance curr.
  • Move to the right child of the popped node.
• Return the dummy node’s right child.

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        dummy = TreeNode(0)
        curr = dummy
        stack = []
        node = root
        
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            
            node = stack.pop()
            node.left = None
            
            curr.right = node
            curr = node
            
            node = node.right
            
        return dummy.right

Complexity

• Time: O(N) as we visit each node exactly once.
• Space: O(H) for the stack, where H is the height of the tree.
• Notes: Iterative approach avoids recursion depth limits and is generally preferred in production environments for robustness.