LeetCode 897 - Increasing Order Search Tree

Difficulty: 🟢 Easy
Topics: Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem gives us the root of a Binary Search Tree, abbreviated as BST, and asks us to rearrange the tree into a very specific form.

A Binary Search Tree has the property that for every node:

All values in the left subtree are smaller
All values in the right subtree are larger

The problem asks us to transform the tree so that:

The smallest value becomes the new root
Every node has no left child
Every node only points to the next larger node through its right child

The final structure should look like a linked list that grows to the right.

Because the tree is a BST, an in-order traversal naturally visits nodes in sorted order. In-order traversal means:

Visit left subtree
Visit current node
Visit right subtree

This is the key observation of the problem. If we visit nodes in-order and reconnect them one by one, we automatically create the required increasing sequence.

For example, consider this BST:

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

Its in-order traversal is:

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

The transformed tree becomes:

The constraints are small:

Number of nodes is between 1 and 100
Node values are between 0 and 1000

Since the tree is small, almost any reasonable traversal solution will pass comfortably. However, the problem is fundamentally about understanding BST traversal and pointer manipulation correctly.

Important edge cases include:

A tree with only one node
A tree already shaped correctly
A tree completely skewed to the left
A tree completely skewed to the right
Ensuring all left pointers are removed, otherwise the structure is incorrect

Approaches

Brute Force Approach

A straightforward solution is to first perform an in-order traversal and store all nodes or values in a list.

Since in-order traversal of a BST produces sorted order, the list will already contain nodes in the desired increasing sequence.

After collecting the nodes, we iterate through the list and reconnect them:

Set each node's left pointer to None
Set each node's right pointer to the next node in the list

The final node points to None.

This approach is easy to understand and implement because it separates traversal from reconstruction. However, it requires extra memory proportional to the number of nodes because all nodes are stored in a list before rebuilding.

Optimal Approach

The better approach is to rebuild the tree during the in-order traversal itself.

Instead of storing all nodes first, we maintain:

A dummy node that acts as the start of the new tree
A pointer called current that always points to the last node added

During traversal:

Traverse left subtree
Disconnect current node's left child
Attach current node to current.right
Move current forward
Traverse right subtree

Because nodes are visited in sorted order, the resulting structure automatically satisfies the increasing order requirement.

This avoids storing all nodes separately and constructs the result incrementally.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Stores all nodes in a list before rebuilding
Optimal	O(n)	O(h)	Rebuilds tree during traversal, recursion stack only

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

Optimal In-Order Reconstruction

Create a dummy node.

The dummy node simplifies handling the head of the new tree. Its right child will eventually point to the smallest node, which becomes the answer. 2. Maintain a pointer called current.

Initially, current points to the dummy node. As we process nodes, current always represents the last node added to the new tree. 3. Perform an in-order traversal.

Since this is a BST, in-order traversal guarantees nodes are visited in ascending order. 4. Recursively traverse the left subtree.

Smaller values must appear before the current node in the final structure. 5. Disconnect the current node's left child.

The problem explicitly requires every node to have no left child. 6. Attach the current node to current.right.

This extends the increasing chain. 7. Move current to the current node.

Future nodes should be attached after this node. 8. Recursively traverse the right subtree.

Larger values come afterward in sorted order. 9. Return dummy.right.

The dummy node itself is artificial. The real transformed tree begins at its right child.

Why it works

The correctness comes from the BST in-order traversal property.

An in-order traversal visits nodes in strictly increasing order. By attaching nodes in the exact order they are visited, we guarantee that every node points to the next larger value.

Because every node's left pointer is explicitly set to None, the resulting structure satisfies all problem requirements.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        dummy = TreeNode(0)
        current = dummy

        def inorder(node: Optional[TreeNode]) -> None:
            nonlocal current

            if not node:
                return

            inorder(node.left)

            node.left = None
            current.right = node
            current = node

            inorder(node.right)

        inorder(root)

        return dummy.right

The solution starts by creating a dummy node and a current pointer. The dummy node makes it easy to return the head of the transformed tree later.

The recursive inorder function performs a standard in-order traversal. The recursion first processes the left subtree so smaller values appear first.

When visiting a node:

Its left pointer is cleared
The node is attached to the right side of current
current moves forward

This incrementally builds the new increasing-order tree.

Finally, the function returns dummy.right, which points to the actual start of the transformed tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func increasingBST(root *TreeNode) *TreeNode {
    dummy := &TreeNode{}
    current := dummy

    var inorder func(node *TreeNode)

    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)

        node.Left = nil
        current.Right = node
        current = node

        inorder(node.Right)
    }

    inorder(root)

    return dummy.Right
}

The Go solution follows the same logic as the Python version.

The main language-specific differences are:

Go uses explicit pointers with *TreeNode
nil is used instead of None
The recursive helper function is declared using a function variable
Closures naturally capture current

No integer overflow concerns exist because node values are very small.

Worked Examples

Example 1

Input:

[5,3,6,2,4,null,8,1,null,null,null,7,9]

The in-order traversal order is:

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

Traversal State

Step	Current Node	New Tree
1	1	1
2	2	1 -> 2
3	3	1 -> 2 -> 3
4	4	1 -> 2 -> 3 -> 4
5	5	1 -> 2 -> 3 -> 4 -> 5
6	6	1 -> 2 -> 3 -> 4 -> 5 -> 6
7	7	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
8	8	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
9	9	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

Final tree:

Example 2

Input:

[5,1,7]

In-order traversal:

1, 5, 7

Traversal State

Step	Current Node	New Tree
1	1	1
2	5	1 -> 5
3	7	1 -> 5 -> 7

Final tree:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack uses tree height

The algorithm processes each node one time during the in-order traversal, so the total running time is linear.

The auxiliary space comes entirely from recursion. In the worst case of a completely skewed tree, the recursion depth becomes O(n). In a balanced tree, the recursion depth is O(log n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def increasingBST(self, root):
        dummy = TreeNode(0)
        current = dummy

        def inorder(node):
            nonlocal current

            if not node:
                return

            inorder(node.left)

            node.left = None
            current.right = node
            current = node

            inorder(node.right)

        inorder(root)

        return dummy.right

def tree_to_list(root):
    result = []

    while root:
        result.append(root.val)

        assert root.left is None  # ensure left child removed

        root = root.right

    return result

sol = Solution()

# Example 1
root1 = TreeNode(
    5,
    TreeNode(
        3,
        TreeNode(2, TreeNode(1)),
        TreeNode(4)
    ),
    TreeNode(
        6,
        None,
        TreeNode(8, TreeNode(7), TreeNode(9))
    )
)
assert tree_to_list(sol.increasingBST(root1)) == [1,2,3,4,5,6,7,8,9]  # complex BST

# Example 2
root2 = TreeNode(5, TreeNode(1), TreeNode(7))
assert tree_to_list(sol.increasingBST(root2)) == [1,5,7]  # simple balanced BST

# Single node
root3 = TreeNode(42)
assert tree_to_list(sol.increasingBST(root3)) == [42]  # minimum size tree

# Left skewed tree
root4 = TreeNode(4,
    TreeNode(3,
        TreeNode(2,
            TreeNode(1)
        )
    )
)
assert tree_to_list(sol.increasingBST(root4)) == [1,2,3,4]  # deep left recursion

# Right skewed tree
root5 = TreeNode(1,
    None,
    TreeNode(2,
        None,
        TreeNode(3)
    )
)
assert tree_to_list(sol.increasingBST(root5)) == [1,2,3]  # already increasing

# Balanced BST
root6 = TreeNode(
    4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(6, TreeNode(5), TreeNode(7))
)
assert tree_to_list(sol.increasingBST(root6)) == [1,2,3,4,5,6,7]  # balanced structure

Test Summary

Test	Why
Complex BST from example 1	Validates full traversal and reconstruction
Small balanced tree	Confirms correct ordering
Single node	Tests minimum input size
Left skewed tree	Tests deep left recursion
Right skewed tree	Tests already-correct structure
Balanced BST	Confirms general correctness

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input. A careless implementation might accidentally disconnect or overwrite the node.

This implementation handles it naturally. The traversal visits the node once, clears its already-empty left child, and returns it as the entire transformed tree.

Completely Left-Skewed Tree

A tree where every node only has a left child creates the maximum recursion depth and tests whether traversal order is handled correctly.

For example:

The algorithm correctly visits nodes in ascending order and reconnects them into:

1 -> 2 -> 3 -> 4

Because every left pointer is explicitly cleared, no leftover connections remain.

Already Increasing Tree

A tree that already satisfies the final structure could expose bugs where pointers are duplicated or cycles are introduced.

For example:

The algorithm still processes nodes safely. Each node is reattached in the same order, and all left pointers remain None.

Ensuring Left Pointers Are Removed

One subtle bug is forgetting to clear node.left.

Even if the right-chain is built correctly, leftover left pointers violate the problem requirements and produce an invalid tree.

This implementation explicitly sets:

node.left = None

for every node during reconstruction, guaranteeing correctness.