LeetCode: 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.

For example:

Input: root = [5,1,7]
Output: [1,null,5,null,7]

Recursive Traverse

For a binary search tree, in-order traverse will get a increased sequence. Recursive traverse will be easy, but we need to store previous node, update the previous node’s right child.

class Solution {
public:
    TreeNode* cur = NULL;
    TreeNode* head = NULL;
    TreeNode* increasingBST(TreeNode* root) {
        cur = NULL;
        iter(root);
        return head;
    }

    void iter(TreeNode* node) {
        if(node->left) iter(node->left);
        if(cur) {
            cur->right = node;
            cur = cur->right;
        } else { 
            cur = node;
            head = cur;
        }
        node->left = NULL;  
        if(node->right) iter(node->right);
    }
};

Iterative version with stack

In-order traverse can also implemented with a stack.

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        stack<TreeNode*> Q;
        TreeNode dummy;
        TreeNode* pre = &dummy;
        TreeNode* cur = root;
        if(root == NULL) return NULL;
        while(!Q.empty() || cur) {
            while(cur) {
                Q.push(cur);
                cur = cur->left;
            }
            cur = Q.top(); Q.pop();
            pre->right = cur;
            pre->left = NULL;
            pre = cur;
            cur = cur->right;
        }
        return dummy.right;
    }
};

Join my Email List for more insights, It's Free!😋

← LeetCode: Divisor Game LeetCode: Max Consecutive Ones →