Increasing Order Search Tree solution and explanation
Google
9 more videos on this problem
Increasing Order Search Tree | Leetcode - 897Algorithms Made Easy · 4:32 · 13K views
Increasing Order Search Tree | Leetcode 897 | BST | Day-17Ayushi Sharma · 11:41 · 7K views
Increasing Order Search Tree -- Leetcode #897elidrinkscoffee · 8:28 · 5K views
Increasing Order Search Tree | Leet code 897 | Theory explained + Python codeSai Anish Malla · 15:16 · 4K views
Increasing Order Search Tree || leetcode 897 || c++ solution || with explanationcode Explainer · 7:54 · 3K views
Increasing Order Search Tree | Leetcode 897 | Live coding session | December leetcode challegeCoding Decoded · 10:48 · 1K views
LeetCode 897. [easy] Increasing Order Search TreeFrancesco Manicardi · 3:37 · 1K views
897 Increasing Order Search Tree | Easy Level Questions Complete Playlist of leetcode in PythonEduEverybody · 9:20 · 827 views
Increasing Order Search Tree | Leetcode 897 | Binary Search Tree 🔥🔥 | Live coding sessionCoding Decoded · 0:53 · 558 views
Daily Leetcode #247: Dec 03, 2020 - 897. Increasing Order Search TreeProgramming Live with Larry · 16:09 · 521 views
The problem
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def increasingBST(root: TreeNode) -> TreeNode:
def inorder(node):
if not node:
return
inorder(node.left)
node.left = None
self.cur.right = node
self.cur = node
inorder(node.right)
dummy = self.cur = TreeNode()
inorder(root)
return dummy.rightclass TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
private TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0);
cur = dummy;
inorder(root);
return dummy.right;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
node.left = null;
cur.right = node;
cur = node;
inorder(node.right);
}
}struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode* dummy = new TreeNode(0);
TreeNode* cur = dummy;
inorder(root, cur);
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);
}
};function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var increasingBST = function(root) {
let dummy = new TreeNode(0);
let cur = dummy;
function inorder(node) {
if (!node) return;
inorder(node.left);
node.left = null;
cur.right = node;
cur = node;
inorder(node.right);
}
inorder(root);
return dummy.right;
};typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* newTreeNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
TreeNode* cur;
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
node->left = NULL;
cur->right = node;
cur = node;
inorder(node->right);
}
TreeNode* increasingBST(TreeNode* root) {
TreeNode* dummy = newTreeNode(0);
cur = dummy;
inorder(root);
return dummy->right;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private TreeNode cur;
public TreeNode IncreasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0);
cur = dummy;
Inorder(root);
return dummy.right;
}
private void Inorder(TreeNode node) {
if (node == null) return;
Inorder(node.left);
node.left = null;
cur.right = node;
cur = node;
Inorder(node.right);
}
}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.
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def increasingBST(root: TreeNode) -> TreeNode:
dummy = TreeNode()
cur = dummy
node = root
while node:
if node.left:
pred = node.left
while pred.right and pred.right != node:
pred = pred.right
if not pred.right:
pred.right = node
node = node.left
else:
pred.right = None
cur.right = node
cur = cur.right
node = node.right
else:
cur.right = node
cur = cur.right
node = node.right
return dummy.rightclass TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0), cur = dummy, node = root;
while (node != null) {
if (node.left != null) {
TreeNode pred = node.left;
while (pred.right != null && pred.right != node) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = node;
node = node.left;
} else {
pred.right = null;
cur.right = node;
cur = cur.right;
node = node.right;
}
} else {
cur.right = node;
cur = cur.right;
node = node.right;
}
}
return dummy.right;
}
}struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode* dummy = new TreeNode(0);
TreeNode* cur = dummy;
TreeNode* node = root;
while (node) {
if (node->left) {
TreeNode* pred = node->left;
while (pred->right && pred->right != node) {
pred = pred->right;
}
if (!pred->right) {
pred->right = node;
node = node->left;
} else {
pred->right = nullptr;
cur->right = node;
cur = cur->right;
node = node->right;
}
} else {
cur->right = node;
cur = cur->right;
node = node->right;
}
}
return dummy->right;
}
};function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var increasingBST = function(root) {
let dummy = new TreeNode(0);
let cur = dummy;
let node = root;
while (node) {
if (node.left) {
let pred = node.left;
while (pred.right && pred.right !== node) {
pred = pred.right;
}
if (!pred.right) {
pred.right = node;
node = node.left;
} else {
pred.right = null;
cur.right = node;
cur = cur.right;
node = node.right;
}
} else {
cur.right = node;
cur = cur.right;
node = node.right;
}
}
return dummy.right;
};#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* increasingBST(TreeNode* root) {
TreeNode* dummy = malloc(sizeof(TreeNode));
dummy->val = 0;
dummy->left = NULL;
TreeNode* cur = dummy;
TreeNode* node = root;
while (node) {
if (node->left) {
TreeNode* pred = node->left;
while (pred->right && pred->right != node) {
pred = pred->right;
}
if (!pred->right) {
pred->right = node;
node = node->left;
} else {
pred->right = NULL;
cur->right = node;
cur = cur->right;
node = node->right;
}
} else {
cur->right = node;
cur = cur->right;
node = node->right;
}
}
return dummy->right;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode IncreasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0);
TreeNode cur = dummy;
TreeNode node = root;
while (node != null) {
if (node.left != null) {
TreeNode pred = node.left;
while (pred.right != null && pred.right != node) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = node;
node = node.left;
} else {
pred.right = null;
cur.right = node;
cur = cur.right;
node = node.right;
}
} else {
cur.right = node;
cur = cur.right;
node = node.right;
}
}
return dummy.right;
}
}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.
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function increasingBST(root: TreeNode | null): TreeNode | null {
const dummy = new TreeNode((right = root));
let prev = dummy;
const dfs = (root: TreeNode | null) => {
if (!root) {
return;
}
dfs(root.left);
prev.right = root;
root.left = null;
prev = root;
dfs(root.right);
};
dfs(root);
return dummy.right;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func increasingBST(root *TreeNode) *TreeNode {
dummy := &TreeNode{Val: 0, Right: root}
prev := dummy
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
prev.Right = root
root.Left = nil
prev = root
dfs(root.Right)
}
dfs(root)
return dummy.Right
}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 | – |
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. |
Frequently asked questions
Is Increasing Order Search Tree easy or hard?
Increasing Order Search Tree is classified as an Easy problem on LeetCode with a high acceptance rate around 78%. The challenge mainly tests understanding of BST in-order traversal and basic tree pointer manipulation.
Increasing Order Search Tree Python/Java solution
Python and Java solutions typically implement recursive in-order traversal with a dummy node pointer to rebuild the tree. Each visited node has its left child set to null and is appended to the right of the previous node, producing the required increasing order tree.
How to solve Increasing Order Search Tree in O(n)?
Perform an in-order traversal of the BST so nodes are processed in sorted order. Maintain a pointer to the previously added node and attach the current node to its right while clearing the left pointer. Since each node is processed once, the total time complexity is O(n).
What is the best approach for Increasing Order Search Tree?
The most common approach uses in-order traversal of the BST and rebuilds the tree during traversal. Because in-order traversal visits nodes in sorted order, you can attach each node to the right of the previous node while setting left pointers to null. This runs in O(n) time and O(h) space where h is the tree height.
Is Increasing Order Search Tree asked at Google/Amazon/Meta?
Problems involving BST traversal and tree restructuring frequently appear in interviews at companies like Amazon, Google, and Meta. This specific problem tests understanding of in-order traversal, pointer manipulation, and binary tree restructuring patterns.
What data structure is used in Increasing Order Search Tree?
The core data structure is a Binary Search Tree. The solution relies on in-order traversal, which may use recursion, an explicit stack, or Morris traversal to visit nodes in sorted order while rebuilding the tree structure.
What is the time complexity of Increasing Order Search Tree?
Both common solutions run in O(n) time because each node in the tree is visited exactly once during the in-order traversal. The recursive version uses O(h) auxiliary space for the recursion stack, while the Morris traversal variant reduces space to O(1).