Leetcode problem 134 - Increasing Order Search Tree

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

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function (root) {
  const nodes = [];

  const traverse = (node) => {
    if (!node) return;
    traverse(node.left);
    nodes.push(node.val);
    traverse(node.right);
  };
  traverse(root);

  const buildTree = (nodes) => {
    if (!nodes.length) return null;
    const tree = new TreeNode(nodes.shift());
    tree.right = buildTree(nodes);
    return tree;
  };

  return buildTree(nodes);
};

The time complexity of this solution is O(n) because we need to traverse all nodes in the binary tree to collect them in sorted order. The space complexity is also O(n) because we are storing all nodes in an array before reconstructing the binary tree.