This problem requires transforming a BST into a right-skewed tree where nodes appear in ascending order. Use an in-order traversal to maintain the correct sequence while reconnecting nodes so each has no left child. Careful state tracking ensures the previous node points to the current node, avoiding cycles or disconnected nodes.
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
How GhostInterview Helps
- Guides through correct in-order traversal sequence and live node reconnection
- Highlights potential failure modes like forgotten left child nullification
- Provides step-by-step reconstruction ensuring the right-skewed BST pattern is maintained efficiently
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Increasing Order Search Tree instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Increasing Order Search Tree from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given a BST and a range, calculate the sum of all node values within that range.
Open problem page#1008 Construct Binary Search Tree from Preorder TraversalConstruct a binary search tree directly from a preorder traversal array using stack-based state tracking efficiently.
Open problem page#783 Minimum Distance Between BST NodesFind the minimum difference between values of two different nodes in a Binary Search Tree using tree traversal and state tracking.
Open problem page