Skip to main content

Increasing Order Search Tree

Given a binary search tree, rearrange the tree such that it forms a linked list where all its values are in ascending order.

Example(s)​

Example 1:

Input:
        5
       / \
      1   6
Output:
1
 \
  5
   \
    6

Example 2:

Input:
       5
      / \
    2    9
   / \ 
  1   3 
Output:
1
 \
  2
   \
    3
     \
      5
       \
        9

Example 3:

Input:
5
 \
  6
Output:
5
 \
  6

Brute Force​

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * Rearrange BST to increasing order using node list
 * @param {TreeNode} root - Root of the BST
 * @return {TreeNode} - Head of the linked list
 */
function increasingBST(root) {
  const nodes = [];
  
  function inorder(node) {
    if (node) {
      inorder(node.left);
      nodes.push(node);
      inorder(node.right);
    }
  }
  
  inorder(root);
  
  for (let i = 0; i < nodes.length - 1; i++) {
    nodes[i].left = null;
    nodes[i].right = nodes[i + 1];
  }
  
  if (nodes.length > 0) {
    nodes[nodes.length - 1].left = null;
    nodes[nodes.length - 1].right = null;
    return nodes[0];
  }
  
  return null;
}

Complexity (Brute Force)​

  • Time Complexity: O(n) - Traversing all nodes
  • Space Complexity: O(n) - Storing all nodes in a list

Optimized Solution​

/**
 * Rearrange BST to increasing order using recursion
 * @param {TreeNode} root - Root of the BST
 * @return {TreeNode} - Head of the linked list
 */
function increasingBSTOptimized(root) {
  const dummy = new TreeNode();
  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;
}

Complexity (Optimized)​

  • Time Complexity: O(n) - Traversing all nodes
  • Space Complexity: O(h) - Recursion stack, where h is tree height

Interactive Code Runner​

Test the Brute Force Solution​

JavaScript Brute Force Solution

function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}

/**
* Rearrange BST to increasing order using node list
* @param {TreeNode} root - Root of the BST
* @return {TreeNode} - Head of the linked list
*/
function increasingBST(root) {
const nodes = [];

function inorder(node) {
  if (node) {
    inorder(node.left);
    nodes.push(node);
    inorder(node.right);
  }
}

inorder(root);

for (let i = 0; i < nodes.length - 1; i++) {
  nodes[i].left = null;
  nodes[i].right = nodes[i + 1];
}

if (nodes.length > 0) {
  nodes[nodes.length - 1].left = null;
  nodes[nodes.length - 1].right = null;
  return nodes[0];
}

return null;
}

// Helper function to create tree from array
function createTree(arr, index = 0) {
if (index >= arr.length || arr[index] === null) return null;
const root = new TreeNode(arr[index]);
root.left = createTree(arr, 2 * index + 1);
root.right = createTree(arr, 2 * index + 2);
return root;
}

// Helper function to convert tree to array (inorder)
function treeToArray(root) {
const result = [];
function inorder(node) {
  if (node) {
    inorder(node.left);
    result.push(node.val);
    inorder(node.right);
  }
}
inorder(root);
return result;
}

// Test cases
const test1 = createTree([5, 1, 6]);
const result1 = increasingBST(test1);
console.log("Tree: [5,1,6] →", treeToArray(result1).join(" -> "));

const test2 = createTree([5, 2, 9, 1, 3]);
const result2 = increasingBST(test2);
console.log("Tree: [5,2,9,1,3] →", treeToArray(result2).join(" -> "));

const test3 = createTree([5, null, 6]);
const result3 = increasingBST(test3);
console.log("Tree: [5,null,6] →", treeToArray(result3).join(" -> "));
Output:
Click "Run Code" to execute the code and see the results.

Test the Optimized Solution​

JavaScript Optimized Solution

function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}

/**
* Rearrange BST to increasing order using recursion
* @param {TreeNode} root - Root of the BST
* @return {TreeNode} - Head of the linked list
*/
function increasingBSTOptimized(root) {
const dummy = new TreeNode();
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;
}

// Helper function to create tree from array
function createTree(arr, index = 0) {
if (index >= arr.length || arr[index] === null) return null;
const root = new TreeNode(arr[index]);
root.left = createTree(arr, 2 * index + 1);
root.right = createTree(arr, 2 * index + 2);
return root;
}

// Helper function to convert tree to array (inorder)
function treeToArray(root) {
const result = [];
function inorder(node) {
  if (node) {
    inorder(node.left);
    result.push(node.val);
    inorder(node.right);
  }
}
inorder(root);
return result;
}

// Test cases
const test1 = createTree([5, 1, 6]);
const result1 = increasingBSTOptimized(test1);
console.log("Tree: [5,1,6] →", treeToArray(result1).join(" -> "));

const test2 = createTree([5, 2, 9, 1, 3]);
const result2 = increasingBSTOptimized(test2);
console.log("Tree: [5,2,9,1,3] →", treeToArray(result2).join(" -> "));

const test3 = createTree([5, null, 6]);
const result3 = increasingBSTOptimized(test3);
console.log("Tree: [5,null,6] →", treeToArray(result3).join(" -> "));
Output:
Click "Run Code" to execute the code and see the results.

Takeaways​

  • In-order traversal ensures ascending order in BST
  • Recursive building with a current pointer optimizes space usage
  • In-place modification by setting left to null and right to next node
  • Dummy node simplifies head handling
  • Edge cases include single node, right-skewed, and left-skewed trees
  • Space optimization from O(n) to O(h) using recursive approach