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:
[1, 100].0 <= Node.val <= 1000The key observation in #897 Increasing Order Search Tree is that a Binary Search Tree (BST) visited using inorder traversal produces nodes in sorted order. The goal is to rearrange the tree so that each node has no left child and only a single right child, effectively forming an increasing sequence of nodes.
A common strategy is to perform an Depth-First Search (DFS) using inorder traversal. As each node is visited, it can be appended to a new tree structure where the previous node’s right pointer connects to the current node, and the left pointer is set to null. This preserves the sorted order while restructuring the tree.
You can implement this either recursively or using an explicit stack for iterative traversal. Both approaches leverage the BST property to process nodes in ascending order. The overall traversal visits each node once, making the solution efficient for large trees.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Inorder DFS (Recursive) | O(n) | O(h) |
| Iterative Inorder using Stack | O(n) | O(h) |
NeetCode
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.
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.
1struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6};
7
8class Solution {
9public:
10 TreeNode* increasingBST(TreeNode* root) {
11 TreeNode* dummy = new TreeNode(0);
12 TreeNode* cur = dummy;
13 inorder(root, cur);
14 return dummy->right;
}
private:
void inorder(TreeNode* node, TreeNode*& cur) {
if (!node) return;
inorder(node->left, cur);
node->left = nullptr;
cur->right = node;
cur = node;
inorder(node->right, cur);
}
};The C++ solution defines a Solution class with a private helper method inorder that is used to traverse and reconstruct the tree. We maintain a current pointer cur which is always set to point to the last added node. We make sure to nullify the left pointers of each node before attaching them to the right of the current pointer.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Inorder traversal of a Binary Search Tree always returns nodes in ascending order. By visiting nodes in this order and relinking them, we can construct the required increasing-order tree structure.
Yes, variations of BST restructuring and inorder traversal problems are commonly asked in FAANG-style interviews. This problem tests understanding of BST properties, DFS traversal, and pointer manipulation.
The optimal approach is to perform an inorder traversal of the BST. Since inorder traversal processes nodes in sorted order, you can reconnect nodes so that each node only points to its right child, forming a right-skewed tree.
A stack or recursion stack is commonly used to implement inorder traversal. These structures help simulate DFS traversal while processing nodes in sorted order from the BST.
In JavaScript, the Morris Traversal technique is applied, manipulating the tree without extra space. We iterate in a while loop, setting predecessors when necessary, allowing for in-order traversal restructuring.