#897

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Increasing Order Search Tree

Rearrange a binary search tree so all nodes follow increasing order with only right children using in-order traversal.

stack tree depth first search binary search tree binary tree

Problem Statement

Given the root of a binary search tree, rearrange it so that all nodes appear in increasing order, with each node having no left child and only one right child. Maintain the original in-order sequence, creating a right-skewed tree that preserves the BST property.

For example, if the input tree is root = [5,3,6,2,4,null,8,1,null,null,null,7,9], the output should be [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9], representing the leftmost node as the new root and all nodes connected only via right pointers.

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 details omitted.

Example 2

Input: root = [5,1,7]

Output: [1,null,5,null,7]

Example details omitted.

Constraints

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

Solution Approach

In-Order DFS Traversal with Node Reconnection

Perform a standard in-order traversal to visit nodes in ascending order. Maintain a pointer to the last visited node to attach the current node as its right child. Set the current node's left child to null to enforce the right-skewed property.

Using a Dummy Node to Simplify Linking

Introduce a dummy node as a precursor to the new root. This allows for simpler reconnection logic since the first real node can be attached to dummy.right, avoiding special handling for the head of the list.

Iterative DFS with Stack for Large Trees

Use an explicit stack to traverse the tree iteratively in-order. Pop nodes from the stack, set their left child to null, and link them to the previous node via the right pointer. This avoids recursion depth issues and still preserves the increasing order sequence.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because every node is visited exactly once during traversal. Space complexity is O(h) for recursion stack or O(n) for iterative stack in the worst case, where h is the tree height and n is the number of nodes.

What Interviewers Usually Probe

Checking for correct in-order traversal and reconnection of nodes
Looking for proper nullification of left children to maintain right-skewed structure
Expecting handling of both recursive and iterative DFS approaches for clarity and efficiency

Common Pitfalls or Variants

Common pitfalls

Forgetting to set left children to null, causing cycles or incorrect tree shape
Not maintaining a previous node reference, which breaks the increasing sequence linkage
Assuming a new array output rather than reconstructing the tree nodes, which is inefficient

Follow-up variants

Create a decreasing order search tree by reversing in-order traversal
Flatten the BST to a linked list in-place with both left and right pointers set to null or used for next node
Apply the same in-order reconstruction approach to a general binary tree, not strictly a BST

FAQ

What is the main goal of the Increasing Order Search Tree problem?

The goal is to transform a BST into a right-skewed tree where all nodes are in ascending order and each node has no left child.

Can this problem be solved iteratively?

Yes, you can use an explicit stack to perform in-order traversal iteratively and link nodes in increasing order.

Why do we need a dummy node in some solutions?

A dummy node simplifies reconnection logic, allowing easy attachment of the first real node without special head handling.

What common mistakes should I avoid when solving this problem?

Ensure left children are set to null, maintain the previous node pointer for linking, and reconstruct nodes rather than just creating an array.

Does this problem require preserving the original BST structure?

No, the original tree structure changes; only the node values and in-order sequence are preserved, resulting in a right-skewed tree.

terminal

Solution

Solution 1: DFS In-order Traversal

We define a virtual node $dummy$, initially the right child of $dummy$ points to the root node $root$, and a pointer $prev$ points to $dummy$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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: TreeNode) -> TreeNode:
        def dfs(root):
            if root is None:
                return
            nonlocal prev
            dfs(root.left)
            prev.right = root
            root.left = None
            prev = root
            dfs(root.right)

        dummy = prev = TreeNode(right=root)
        dfs(root)
        return dummy.right

Continue Practicing

#938 range sum of bst #1008 construct binary search tree from preorder traversal #783 minimum distance between bst nodes