Increasing Order Search Tree
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach first performs a standard in-order traversal of the Binary Search Tree. During the traversal, it stores all the node values in an auxiliary list. Since it's a BST, an in-order traversal naturally yields the values in ascending order. After collecting all the values, a new tree is constructed from this sorted list. The new tree is a skewed tree where each node only has a right child.
Algorithm
- Initialize an empty
ArrayListto store the node values. - Define a recursive helper function,
inorder(node, list), to perform the in-order traversal. - In the
inorderfunction:- Base case: If the current node is
null, return. - Recursively traverse the left subtree:
inorder(node.left, list). - Add the current node's value to the list:
list.add(node.val). - Recursively traverse the right subtree:
inorder(node.right, list).
- Base case: If the current node is
- Call the
inorderfunction starting from theroot. - After the traversal, create a new dummy
TreeNodewhich will act as a placeholder for the head of the new tree. - Create a pointer,
currentNode, and point it to the dummy node. - Iterate through the list of sorted values. For each value:
- Create a new
TreeNodewith this value. - Set
currentNode.rightto this new node. - Move
currentNodeto its new right child (currentNode = currentNode.right).
- Create a new
- Finally, return
dummyNode.right, which is the root of the newly formed skewed tree.
Walkthrough
The simplest way to solve the problem is to separate the traversal from the construction. We can perform an in-order traversal to get all the nodes' values in a sorted manner and store them in a list. Then, we can iterate through this list and build a new tree structure as required, where each node is the right child of the previous one.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode increasingBST(TreeNode root) { List<Integer> vals = new ArrayList<>(); inorder(root, vals); TreeNode dummyNode = new TreeNode(-1); TreeNode currentNode = dummyNode; for (int val : vals) { currentNode.right = new TreeNode(val); currentNode = currentNode.right; } return dummyNode.right; } private void inorder(TreeNode node, List<Integer> vals) { if (node == null) { return; } inorder(node.left, vals); vals.add(node.val); inorder(node.right, vals); }}Complexity
Time
O(N), where N is the number of nodes in the tree. The in-order traversal takes O(N) time to visit every node. Building the new tree from the list also takes O(N) time.
Space
O(N), where N is the number of nodes. We use an `ArrayList` to store all N node values. Additionally, the recursion stack for the in-order traversal can go up to O(H) where H is the height of the tree. In the worst case of a skewed tree, H can be N, making the total space complexity O(N).
Trade-offs
Pros
Simple to understand and implement.
Clearly separates the logic of traversal and tree construction.
Cons
Uses significant extra space (O(N)) for the list.
Creates entirely new nodes, which is less efficient than modifying the existing tree structure in-place.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private TreeNode prev ; public TreeNode increasingBST ( TreeNode root ) { TreeNode dummy = new TreeNode ( 0 , null , root ); prev = dummy ; dfs ( root ); return dummy . right ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); prev . right = root ; root . left = null ; prev = root ; dfs ( root . right ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.