LeetCode 897. Increasing Order Search Tree (javascript solution)

#algorithms #javascript

Description:

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.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

var increasingBST = function(root) {
    // Create dummy head
    let ans = new TreeNode(0);
    // Pointer to the current node
    let cur = ans;
    // Add node to the right pointer of cur and remove the left pointer of cur then change cur to point to node
    function inorder(node) {
        if (node === null) return;
        inorder(node.left);
        node.left = null;
        cur.right = node;
        cur = node;
        inorder(node.right);
    }
    inorder(root);
    return ans.right;
}