Problem Description

You are given the root of a binary search tree (BST). Your task is to rearrange the tree into a special form where:

1. The tree follows in-order traversal sequence (left → root → right)
2. The leftmost node (smallest value) becomes the new root
3. Every node has no left child - all left pointers should be null
4. Every node has at most one right child
5. The resulting structure forms a "right-skewed" tree that looks like a linked list

Essentially, you need to flatten the BST into a chain where nodes are connected only through their right pointers, and the nodes appear in ascending order (since it's a BST and we use in-order traversal).

For example, if you have a BST like:

      5
     / \
    3   6
   / \   \
  2   4   8
 /       / \
1       7   9

After rearrangement, it should become:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                9

The values appear in sorted order (1→2→3→4→5→6→7→8→9), and each node only has a right child, forming a linear structure.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While this is a binary search tree problem, a tree is a special type of graph (specifically, a connected acyclic graph). Trees have nodes and edges connecting parent-child relationships.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary search tree (BST). We have a root node and each node has at most two children (left and right).

DFS

• Yes: Since we're dealing with a tree and need to traverse it, DFS (Depth-First Search) is the appropriate algorithm.

Conclusion: The flowchart leads us directly to using DFS for this problem.

This makes perfect sense because:

1. We need to visit every node in the tree to rearrange them
2. We need to follow in-order traversal (left → root → right), which is a specific type of DFS
3. DFS allows us to recursively process the left subtree, then the current node, then the right subtree, which perfectly matches the in-order traversal pattern needed
4. During the traversal, we can modify the tree structure by adjusting the left and right pointers to create the desired "right-skewed" linked list structure

The DFS approach with in-order traversal ensures we process nodes in ascending order (due to BST properties), allowing us to build the resulting structure correctly.

Intuition

The key insight comes from understanding what the problem is really asking: we need to transform a BST into a linked list where nodes are connected only through right pointers, and the values must be in ascending order.

Since we need ascending order and we're working with a BST, in-order traversal immediately comes to mind because it visits nodes in sorted order (left → root → right).

Now, how do we transform the tree while traversing? Think about building a linked list - we need to keep track of the "previous" node so we can connect it to the current node. This suggests we need a pointer that remembers the last node we processed.

Here's the clever part: instead of collecting all nodes first and then rebuilding the tree, we can modify the tree structure during the traversal itself. As we visit each node in in-order:

1. Connect the previous node's right pointer to the current node
2. Clear the current node's left pointer (set to null)
3. Update our "previous" pointer to the current node

But there's a small problem - what about the very first node? We don't have a "previous" node initially. This is where the dummy node technique comes in handy. We create a dummy node whose right child initially points to the root. This dummy node acts as our initial "previous" node, solving the edge case elegantly.

The beauty of this approach is that by the time we finish the in-order traversal, we've transformed the entire tree into the desired structure. The dummy node's right child now points to the new root (the smallest element), and all nodes are connected in a chain through their right pointers.

This solution is elegant because it leverages the natural order of in-order traversal and modifies the tree in-place during a single pass, achieving both the traversal and transformation simultaneously.

Learn more about Stack, Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

Let's walk through the implementation step by step, building on our DFS in-order traversal approach.

Initial Setup: We create a dummy node and a prev pointer, both initially pointing to the same dummy node. The dummy node's right child points to the original root. This setup handles the edge case of connecting the first (smallest) node.

dummy = prev = TreeNode(right=root)

The DFS Function: We define a recursive DFS function that performs in-order traversal:

def dfs(root):
    if root is None:
        return
    nonlocal prev
    dfs(root.left)    # Process left subtree
    # Process current node
    prev.right = root
    root.left = None
    prev = root
    dfs(root.right)   # Process right subtree

How the Traversal Works:

1. Base Case: If the current node is None, we simply return.

2. Left Subtree: We first recursively process the entire left subtree with dfs(root.left). This ensures all smaller values are processed first.

3. Current Node Processing: After the left subtree is done:

   • prev.right = root: Connect the previous node's right pointer to the current node
   • root.left = None: Remove the left child of the current node (as required)
   • prev = root: Update prev to point to the current node for the next iteration

4. Right Subtree: Finally, process the right subtree with dfs(root.right).

The Magic of nonlocal: The nonlocal prev declaration allows the nested function to modify the prev variable from the outer scope, maintaining state across recursive calls.

Example Walkthrough: For a simple BST:

    2
   / \
  1   3

1. Start with dummy → root(2)
2. Process left subtree: reach node 1
3. Connect: dummy.right = 1, clear 1.left, prev = 1
4. Back to node 2: Connect: 1.right = 2, clear 2.left, prev = 2
5. Process right subtree: reach node 3
6. Connect: 2.right = 3, clear 3.left, prev = 3

Result: dummy → 1 → 2 → 3

Return Value: After the traversal completes, we return dummy.right, which now points to the new root (the smallest element in the BST).

The time complexity is O(n) as we visit each node once, and the space complexity is O(h) where h is the height of the tree, due to the recursion stack.

Example Walkthrough

Let's walk through a concrete example to see how the solution transforms a BST step by step.

Initial BST:

    4
   / \
  2   5
 / \
1   3

Goal: Transform into a right-skewed tree: 1 → 2 → 3 → 4 → 5

Setup:

• Create dummy node with value 0 (arbitrary)
• Set prev = dummy
• Connect dummy.right = root(4)

Initial state:

dummy(0) → 4
           / \
          2   5
         / \
        1   3

Step-by-step DFS Execution:

Step 1: dfs(4) called

• First, recursively call dfs(2) (left subtree)

Step 2: dfs(2) called

• First, recursively call dfs(1) (left subtree)

Step 3: dfs(1) called

• dfs(None) for left child - returns immediately
• Process node 1:
  • prev.right = 1 (dummy now points to 1)
  • 1.left = None (already None)
  • prev = 1 (update prev pointer)
• dfs(None) for right child - returns immediately

Current structure:

dummy(0) → 1

Step 4: Back to dfs(2), process node 2

• Left subtree done
• Process node 2:
  • prev.right = 2 (node 1 now points to 2)
  • 2.left = None (disconnect from node 1)
  • prev = 2 (update prev pointer)
• Call dfs(3) for right subtree

Current structure:

dummy(0) → 1 → 2

Step 5: dfs(3) called

• dfs(None) for left child - returns immediately
• Process node 3:
  • prev.right = 3 (node 2 now points to 3)
  • 3.left = None (already None)
  • prev = 3 (update prev pointer)
• dfs(None) for right child - returns immediately

Current structure:

dummy(0) → 1 → 2 → 3

Step 6: Back to dfs(4), process node 4

• Left subtree done
• Process node 4:
  • prev.right = 4 (node 3 now points to 4)
  • 4.left = None (disconnect from node 2)
  • prev = 4 (update prev pointer)
• Call dfs(5) for right subtree

Current structure:

dummy(0) → 1 → 2 → 3 → 4

Step 7: dfs(5) called

• dfs(None) for left child - returns immediately
• Process node 5:
  • prev.right = 5 (node 4 now points to 5)
  • 5.left = None (already None)
  • prev = 5 (update prev pointer)
• dfs(None) for right child - returns immediately

Final structure:

dummy(0) → 1 → 2 → 3 → 4 → 5

Return: dummy.right which is node 1, the new root of our transformed tree.

The key insight is that in-order traversal naturally visits nodes in ascending order for a BST. By maintaining a prev pointer and connecting nodes as we visit them, we build the right-skewed tree incrementally. The dummy node elegantly handles the edge case of connecting to the first (smallest) node.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs an in-order traversal of the binary search tree using DFS (Depth-First Search). During this traversal, each node is visited exactly once. For each node visit, the operations performed are:

• Checking if the node is None: O(1)
• Recursively calling dfs on left and right children
• Reassigning pointers (prev.right = root, root.left = None, prev = root): O(1)

Since we visit all n nodes exactly once and perform constant-time operations at each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity comes from the recursive call stack used during the DFS traversal. In the worst case, when the tree is completely unbalanced (essentially a linked list), the recursion depth can be O(n). In the best case of a balanced tree, the recursion depth would be O(log n). However, considering the worst-case scenario, the space complexity is O(n).

Additionally, the algorithm modifies the tree in-place and only uses a constant amount of extra space for the dummy and prev variables, which doesn't affect the overall space complexity dominated by the recursion stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Clear Left Pointers

The Problem: A common mistake is connecting nodes correctly through their right pointers but forgetting to set node.left = None. This results in a tree that still has left children, violating the requirement that all nodes should have no left child.

Incorrect Code:

def inorder_traverse(node):
    if node is None:
        return
    nonlocal prev
    inorder_traverse(node.left)
    prev.right = node
    # FORGOT: node.left = None  ← Missing this line!
    prev = node
    inorder_traverse(node.right)

Why It Happens: When focusing on building the right-skewed chain, it's easy to overlook that the original left pointers are still intact. The nodes get connected correctly via right pointers, but the old left connections remain.

The Fix: Always remember to explicitly set node.left = None after connecting the node to the chain:

prev.right = node
node.left = None  # Critical: Clear the left pointer
prev = node

Pitfall 2: Not Using nonlocal for the prev Variable

The Problem: Without the nonlocal declaration, the inner function creates a local prev variable instead of modifying the outer scope's prev. This breaks the chain-building logic entirely.

Incorrect Code:

def increasingBST(self, root):
    dummy = prev = TreeNode(right=root)
  
    def inorder_traverse(node):
        if node is None:
            return
        # FORGOT: nonlocal prev  ← Missing this line!
        inorder_traverse(node.left)
        prev.right = node  # This creates a local 'prev' or throws an error
        node.left = None
        prev = node
        inorder_traverse(node.right)
  
    inorder_traverse(root)
    return dummy.right

Why It Happens: Python's scoping rules require explicit declaration when modifying variables from an enclosing scope. Without nonlocal, Python either creates a new local variable or throws an UnboundLocalError.

The Fix: Always declare nonlocal prev at the beginning of the inner function:

def inorder_traverse(node):
    if node is None:
        return
    nonlocal prev  # Essential for modifying outer scope variable
    # ... rest of the code

Pitfall 3: Incorrect Dummy Node Initialization

The Problem: Creating the dummy node incorrectly or forgetting to initialize prev to point to it can cause the first node to be disconnected from the result.

Incorrect Code:

# Wrong: Separate initialization
dummy = TreeNode()
prev = TreeNode()  # Different node!
dummy.right = root

# Or forgetting to set dummy.right
dummy = prev = TreeNode()  # No connection to root

Why It Happens: The dummy node pattern requires careful setup. The dummy and prev must initially reference the same node, and the dummy should not initially point to the root (since we'll rebuild the connections).

The Fix: Use a single line initialization that creates one dummy node and assigns it to both variables:

dummy = prev = TreeNode()  # Both point to same dummy node
# Don't set dummy.right = root here; let the traversal handle it

Complete Corrected Solution:

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def inorder_traverse(node):
            if node is None:
                return
          
            nonlocal prev  # Don't forget this!
          
            inorder_traverse(node.left)
          
            prev.right = node
            node.left = None  # Don't forget to clear left pointer!
            prev = node
          
            inorder_traverse(node.right)
      
        dummy = prev = TreeNode()  # Correct initialization
        inorder_traverse(root)
        return dummy.right