LeetCode 897: Increasing Order Search Tree

Problem Restatement

We are given the root of a binary search tree.

We need to rearrange the tree in inorder order so that:

Requirement	Meaning
New root	The leftmost node of the original tree
Left child	Every node must have no left child
Right child	Each node may have one right child
Order	Nodes appear in increasing order

The result should be a right-skewed tree, like a sorted linked list using only right pointers. The official problem states that every node should have no left child and only one right child.

Input and Output

Item	Meaning
Input	`root`, the root of a binary search tree
Output	Root of the rearranged increasing order tree
Tree type	Binary search tree
Node values	Rearranged in increasing order
Left pointers	Must all become `None`

Function shape:

def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    ...

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]

The original tree is:

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

The result is:

Example 2:

Input:  root = [5,1,7]
Output: [1,null,5,null,7]

The inorder order is:

1, 5, 7

So the result is a right-only chain:

1 -> 5 -> 7

First Thought: Store Values, Then Rebuild

A simple approach is:

Run inorder traversal.
Store all node values in a list.
Build a new right-skewed tree from the sorted values.

Because the input is a binary search tree, inorder traversal visits values in increasing order.

Code idea:

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

        def inorder(node):
            if not node:
                return

            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)

        dummy = TreeNode(0)
        curr = dummy

        for value in values:
            curr.right = TreeNode(value)
            curr = curr.right

        return dummy.right

This works, but it creates new nodes and stores all values.

We can rearrange the existing nodes directly.

Key Insight

A binary search tree’s inorder traversal visits nodes in increasing order.

So while doing inorder traversal, we can connect each visited node to the previous visited node:

previous.right = current
current.left = None

We use a dummy node before the first real node.

The dummy node makes it easy to attach the first visited node without special handling.

Algorithm

Create:

dummy = TreeNode(0)
prev = dummy

Run inorder traversal.

When visiting a node:

Visit the left subtree first.
Attach the current node after prev.
Set node.left = None.
Move prev to the current node.
Visit the right subtree.

At the end, return:

dummy.right

This is the smallest node in the original tree.

Walkthrough

Use:

root = [5,1,7]

Inorder traversal visits:

1, 5, 7

Start:

dummy -> None
prev = dummy

Visit 1:

dummy.right = 1
1.left = None
prev = 1

Visit 5:

1.right = 5
5.left = None
prev = 5

Visit 7:

5.right = 7
7.left = None
prev = 7

Return:

dummy.right

which is node 1.

The final tree is:

1 -> 5 -> 7

using only right pointers.

Correctness

Because the input tree is a binary search tree, inorder traversal visits its nodes in strictly increasing sorted order.

The algorithm processes nodes exactly in that inorder sequence.

Whenever it visits a node, it attaches that node as the right child of the previously visited node. Therefore, the right pointers in the output follow the inorder sequence.

The algorithm also sets each visited node’s left child to None, so no node in the output has a left child.

The dummy node’s right child is set to the first inorder node, which is the smallest node in the original tree. Therefore, the returned root is the required leftmost node.

Every original node is visited once and attached once, so the output contains exactly all original nodes in increasing order.

Thus, the algorithm returns the required increasing order search tree.

Complexity

Let:

n = number of nodes
h = height of the tree

Metric	Value	Why
Time	`O(n)`	Each node is visited once
Space	`O(h)`	Recursion stack depth is the tree height

For a balanced tree, h = O(log n). For a skewed tree, h = O(n).

Implementation

# 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

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

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

            if not node:
                return

            inorder(node.left)

            prev.right = node
            node.left = None
            prev = node

            inorder(node.right)

        inorder(root)

        return dummy.right

Code Explanation

We create a dummy node:

dummy = TreeNode(0)
prev = dummy

prev always points to the last node added to the new right-only tree.

The traversal is inorder:

inorder(node.left)

This visits smaller nodes first.

When we visit the current node, we attach it after prev:

prev.right = node

Then we remove its left child:

node.left = None

This is required because the output tree must have no left children.

Now the current node becomes the last node in the chain:

prev = node

Then we visit the right subtree:

inorder(node.right)

At the end, the dummy node’s right child is the new root:

return dummy.right

Tail-Recursive Style Alternative

Another elegant version passes a tail node.

It returns the head of the rearranged subtree, and connects the largest node of the subtree to tail.

class Solution:
    def increasingBST(
        self,
        root: Optional[TreeNode],
        tail: Optional[TreeNode] = None
    ) -> Optional[TreeNode]:
        if not root:
            return tail

        result = self.increasingBST(root.left, root)

        root.left = None
        root.right = self.increasingBST(root.right, tail)

        return result

This version also rearranges the original nodes in place.

Testing

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

def to_right_chain(root):
    values = []

    while root:
        assert root.left is None
        values.append(root.val)
        root = root.right

    return values

def run_tests():
    s = Solution()

    root = TreeNode(
        5,
        TreeNode(1),
        TreeNode(7)
    )
    ans = s.increasingBST(root)
    assert to_right_chain(ans) == [1, 5, 7]

    root = TreeNode(
        5,
        TreeNode(
            3,
            TreeNode(2, TreeNode(1)),
            TreeNode(4)
        ),
        TreeNode(
            6,
            None,
            TreeNode(8, TreeNode(7), TreeNode(9))
        )
    )
    ans = s.increasingBST(root)
    assert to_right_chain(ans) == [1, 2, 3, 4, 5, 6, 7, 8, 9]

    root = TreeNode(1)
    ans = s.increasingBST(root)
    assert to_right_chain(ans) == [1]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[5,1,7]`	Small BST example
Larger BST	Checks full inorder chain
Single node	Minimum tree
`left is None` assertion	Confirms output has no left children