Design Gurus Logo
Increasing Order Search Tree (easy)

Problem Statement

Given a root node of the binary search tree, rearrange the BST in in-order such that left-most node becomes the root node of the tree, and each node has only one right child but no left child.

Examples

Example 1:

  • Input: root = [2,1,4,null,null,3]
Image
  • Expected Output: [1,null,2,null,3,null,4]
  • Justification: The original tree has the root at 2, with 1 as the left child and a subtree rooted at 4 with 3 as its left child. The rearranged tree starts with 1, then proceeds to 2, followed by 3, and ends with 4, each as the right child of the previous.

Example 2:

  • Input: root = [3,2,5,1,null,4,6]
  • Expected Output: [1,null,2,null,3,null,4,null,5,null,6]
  • Justification: Starting from 1 (the smallest value), each node is connected to the next higher value as its right child until the highest value, 6, is reached.

Example 3:

  • Input: root = [1,null,2,null,3,null,4,null,5]
  • Expected Output: [1,null,2,null,3,null,4,null,5]
  • Justification: The input tree is already a right-skewed tree representing an ascending order sequence. Therefore, the output remains the same as the input.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory