Increasing Order Search Tree — Problem & Solution
Increasing Order Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Increasing Order Search Tree is an easy coding problem on depth-first search, trees and stack, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees, Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree.
Rearrange the tree so that it becomes a chain in increasing (in-order) order: the node with the smallest value is the new root, no node has a left child, and every node's right child is the node that follows it in order. Return the new root.
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]
Explanation: In order the values are 1, 2, …, 9; each becomes the right child of the one before.
Example 2
Input: root = [5,1,7]
Output: [1,null,5,null,7]
Explanation: In order: 1, 5, 7.
Example 3
Input: root = [1]
Output: [1]
Explanation: A single node is already a chain.
Constraints
1 <= number of nodes <= 1000 <= Node.val <= 1000all node values are distinct
Hints for Increasing Order Search Tree
Hint 1
In a binary search tree the in-order traversal visits the values in increasing order — that order is exactly the chain you need.
Hint 2
Traverse in order and link each visited node as the right child of the previously visited one.
Hint 3
A dummy head makes the first link like every other; clear each node's left pointer as you link it.
How to solve Increasing Order Search Tree
The required chain is the in-order sequence of the tree. Walk the tree in order and splice each node onto the end of the chain built so far, reusing the nodes themselves.
Approach
- Create a dummy node and keep
tailpointing at it. - Traverse in order with an explicit stack: push left children down to the leftmost node, pop a node, then continue from its right child.
- For every popped node: set its left pointer to null, make it
tail.right, and movetailto it. - Return
dummy.right.
Why it works
When a node is popped its whole left subtree has already been emitted, and its right child was read into the traversal before tail.right is ever overwritten, so relinking never loses a node. The last node popped is the largest, whose right pointer is already null.
Complexity
- Time —
O(n) - Space —
O(h) for the stack, h the height
Pitfalls
- Forgetting to clear the left pointers leaves cycles or stray branches in the output.
- Read a node's right child before relinking — or, as here, link the node only after it is popped, when its right child is the next thing to visit.
Reference solution
Python
from typing import Optional
def increasingBST(root: Optional[TreeNode]) -> Optional[TreeNode]:
dummy = TreeNode(0)
tail = dummy
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
node.left = None
tail.right = node
tail = node
node = node.right
return dummy.rightJava
public static TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0), tail = dummy;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
node.left = null;
tail.right = node;
tail = node;
node = node.right;
}
return dummy.right;
}C++
TreeNode* increasingBST(TreeNode* root) {
TreeNode dummy(0);
TreeNode* tail = &dummy;
vector<TreeNode*> stack;
TreeNode* node = root;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back();
stack.pop_back();
node->left = nullptr;
tail->right = node;
tail = node;
node = node->right;
}
return dummy.right;
}JavaScript
var increasingBST = function(root) {
var dummy = new TreeNode(0), tail = dummy;
var stack = [], node = root;
while (stack.length > 0 || node !== null) {
while (node !== null) { stack.push(node); node = node.left; }
node = stack.pop();
node.left = null;
tail.right = node;
tail = node;
node = node.right;
}
return dummy.right;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals