Increasing Order Search Tree - Solution & Explanation
Problem Statement
Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
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 2:
Input: root = [5,1,7] Output: [1,null,5,null,7]
Constraints:
- The number of nodes in the given tree will be in the range
[1, 100]. 0 <= Node.val <= 1000
Approach Overview
Problem Overview: You are given the root of a Binary Search Tree. The goal is to rearrange the tree so that it becomes an increasing order tree where every node has no left child and only one right child. The resulting structure should follow the in-order sequence of the original BST.
Approach 1: In-Order Traversal with Recursion (Time: O(n), Space: O(h))
A Binary Search Tree naturally produces values in sorted order when traversed using in-order traversal. That property makes this problem straightforward: perform an in-order traversal and rebuild the tree while visiting nodes. Maintain a dummy node and a pointer called current. Each time you visit a node, set node.left = null, attach it to current.right, and move the pointer forward.
This approach uses recursion to traverse the tree depth-first, which implicitly uses the call stack. The recursion depth is proportional to the tree height h. For balanced trees this is O(log n), but in the worst case (skewed tree) it becomes O(n). The algorithm touches each node exactly once, so the time complexity remains O(n).
This method is easy to reason about and commonly used in interviews. It relies on the classic Depth-First Search traversal pattern and works well when recursion is acceptable.
Approach 2: Morris In-Order Traversal (Time: O(n), Space: O(1))
Morris traversal performs in-order traversal without recursion or an explicit stack. Instead, it temporarily modifies the tree by creating threaded links between nodes. For each node, find its inorder predecessor in the left subtree. If the predecessor's right pointer is null, create a temporary link back to the current node and move left. If the link already exists, remove it, process the node, and move right.
While visiting nodes in sorted order, restructure the tree the same way as the recursive solution: set left = null and attach nodes sequentially using a running pointer. Because Morris traversal eliminates recursion and auxiliary stacks, the extra space usage becomes O(1).
The tradeoff is implementation complexity. Morris traversal requires careful pointer manipulation and temporary structural changes, which can introduce bugs if handled incorrectly. However, it is valuable when memory constraints matter or when interviewers specifically ask for constant extra space.
Recommended for interviews: Start with the recursive in-order traversal. It clearly demonstrates your understanding of BST ordering and DFS traversal. After presenting the O(n) time, O(h) space solution, mention Morris traversal as the optimized follow-up that reduces space to O(1). Interviewers usually expect the recursive solution first, while the Morris version shows deeper understanding of tree traversal techniques.
Approach 1: Approach 1: In-Order Traversal with Recursion
This approach involves performing an in-order traversal to visit the nodes of the tree in sorted order. As we visit each node, we rearrange the nodes to form a new tree where each node only has a right child.
We will use a dummy node that helps us easily chain the nodes in the desired manner. During the traversal, we append each node to the right of the previous node.
In the Python solution, we define a helper function inorder that performs an in-order traversal. We pass each node to this function to rearrange the nodes by severing the left child and linking the nodes to the right child of the current node pointed by self.cur.
The dummy node acts as a placeholder to return the new root of the tree.
Complexity
Time Complexity: O(n), where n is the number of nodes, as we visit each node once.
Space Complexity: O(n), due to the recursion stack space where n is the number of nodes.
Approach 2: Approach 2: Morris In-Order Traversal
A space-optimized approach to perform in-order traversal without recursion or a stack is Morris Traversal. This involves temporarily modifying the tree structure by linking the in-order predecessor of each node to the node itself, allowing us to traverse the tree without additional space.
During the traversal, we reconstruct the tree in the desired form by altering the left and right pointers.
The Python solution employs Morris Traversal to achieve O(1) space complexity. We use a while loop to traverse the tree while altering the pointers as described. When there's a left subtree, we find the predecessor, link it, and then follow the same logic until the tree is reconstructed in the desired order.
Complexity
Time Complexity: O(n), as each node is processed a constant number of times (at most twice).
Space Complexity: O(1), as we are not using any extra space other than a couple of pointers.
Approach 3: 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.
We perform an in-order traversal on the binary search tree. During the traversal, each time we visit a node, we point the right child of prev to it, then set the left child of the current node to null, and assign the current node to prev for the next traversal.
After the traversal ends, the original binary search tree is modified into a singly linked list with only right child nodes. We then return the right child of the virtual node dummy.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary search tree.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: In-Order Traversal with Recursion | Time Complexity: O(n), where n is the number of nodes, as we visit each node once. Space Complexity: O(n), due to the recursion stack space where n is the number of nodes. |
| Approach 2: Morris In-Order Traversal | Time Complexity: O(n), as each node is processed a constant number of times (at most twice). Space Complexity: O(1), as we are not using any extra space other than a couple of pointers. |
| DFS In-order Traversal | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Order Traversal with Recursion | O(n) | O(h) | Best general solution. Easy to implement and ideal for interviews when recursion is allowed. |
| Morris In-Order Traversal | O(n) | O(1) | Use when constant extra space is required or recursion/stack usage must be avoided. |
Video Solution
Increasing Order Search Tree | Leetcode - 897 • Algorithms Made Easy • 13,839 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Increasing Order Search Tree easy or hard?
Increasing Order Search Tree Python/Java solution
How to solve Increasing Order Search Tree in O(n)?
What is the best approach for Increasing Order Search Tree?
Is Increasing Order Search Tree asked at Google/Amazon/Meta?
What data structure is used in Increasing Order Search Tree?
What is the time complexity of Increasing Order Search Tree?
Ready to solve this problem?
Practice Increasing Order Search Tree with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor