Increasing Order Search Tree

Easy
1881.

Increasing Order Search Tree

Increasing Order Search Tree is an easy coding problem on depth-first search, trees and stack, asked in Amazon and Google interviews.

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 <= 100
  • 0 <= Node.val <= 1000
  • all node values are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 0 <= Node.val <= 1000
  • all node values are distinct

Hints for Increasing Order Search Tree

  1. 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.

  2. Hint 2

    Traverse in order and link each visited node as the right child of the previously visited one.

  3. 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

  1. Create a dummy node and keep tail pointing at it.
  2. Traverse in order with an explicit stack: push left children down to the leftmost node, pop a node, then continue from its right child.
  3. For every popped node: set its left pointer to null, make it tail.right, and move tail to it.
  4. 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.right

Java

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