897. Increasing Order Search Tree

Description of the Problem

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

Solution

Code(C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if (root == nullptr)
            return nullptr;
        else if (root->left == nullptr){
            TreeNode * right = increasingBST(root->right);
            TreeNode * mid = new TreeNode(root->val);
            mid->right = right;
            return mid;
        }
        else{
            TreeNode * left = increasingBST(root->left);
            TreeNode * right = increasingBST(root->right);
            TreeNode * mid = new TreeNode(root->val);
            TreeNode * leftLeaf = left;
            while(leftLeaf -> right != nullptr)
                leftLeaf = leftLeaf->right;

            leftLeaf->right = mid;
            mid->right = right;
            return left;
        }
    }
};

Complexity

• \(h\) is the height of the tree
• \(n\) is the number of nodes in the tree

Time complexity:

• \( T(n) = O(n) \)
  • Traverse all nodes in the tree.

Auxiliary Space:

• \( S(h) = O(h) \)
  • the depth of the tree is the depth of recursive tree.