Increasing Order Search Tree

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem

Rearrange the BST so that the leftmost node is the new root and every node has no left child.

Solutions

# Python
def increasingBST(root):
    dummy = TreeNode(0)
    cur = [dummy]
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        node.left = None
        cur[0].right = node
        cur[0] = node
        inorder(node.right)
    inorder(root)
    return dummy.right
// C++
TreeNode* cur;
TreeNode* increasingBST(TreeNode* root) {
    TreeNode dummy(0); cur = &dummy;
    inorder(root);
    return dummy.right;
}
void inorder(TreeNode* node) {
    if (!node) return;
    inorder(node->left);
    node->left = nullptr; cur->right = node; cur = node;
    inorder(node->right);
}
// Java
TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
    TreeNode dummy = new TreeNode(0); cur = dummy;
    inorder(root);
    return dummy.right;
}
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    node.left = null; cur.right = node; cur = node;
    inorder(node.right);
}
// JavaScript
function increasingBST(root) {
    const dummy = new TreeNode(0);
    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

  • Time: O(n), Space: O(h)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro