algoadvance

Leetcode 897. Increasing Order Search Tree

Problem Statement

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.

Clarifying Questions

  1. What are the constraints on the values within the nodes?
    • The values within the nodes are unique.
  2. What is the size range for the tree?
    • The number of nodes in the tree will be in the range [1, 100].
  3. Do we need to handle any cases where the tree is invalid or null?
    • The problem guarantees a non-null root within the specified node range.
  4. Is there a specific output structure or format required?
    • The output should be the new root of the modified tree structured as described.

Strategy

To solve this problem, we will employ an in-order traversal to visit the nodes of the tree in ascending order. During the traversal, we will rebuild the tree such that each node only has a right child.

Here is the step-by-step approach:

  1. In-Order Traversal: Traverse the tree using in-order traversal to ensure that nodes are processed in ascending order.
  2. Reconstruction: As we traverse the tree, reconstruct it such that each node only has a right child.

To implement this, we’ll maintain a dummy node that helps in reconstructing the tree. We will use a current pointer that starts at the dummy node and moves right as we attach nodes to the new tree.

Code

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if (!root) return nullptr;

        TreeNode* dummy = new TreeNode(0);
        TreeNode* current = dummy;

        inorderTraversal(root, current);

        return dummy->right;
    }

private:
    void inorderTraversal(TreeNode* node, TreeNode*& current) {
        if (!node) return;

        inorderTraversal(node->left, current);

        // At this point, node is the next node in inorder sequence
        node->left = nullptr; // We do not need left children in the new tree
        current->right = node; // Attach current's right to node
        current = node; // Move current

        inorderTraversal(node->right, current);
    }
};

// Helper function to create a new TreeNode
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// Helper function to print the resulting tree (for testing)
void printRightSkewedTree(TreeNode* root) {
    TreeNode* current = root;
    while (current) {
        std::cout << current->val << " ";
        current = current->right;
    }
}

int main() {
    // Example usage
    Solution sol;
    
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->right = createNode(6);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->left->left->left = createNode(1);
    root->right->right = createNode(8);
    root->right->right->left = createNode(7);
    root->right->right->right = createNode(9);

    TreeNode* result = sol.increasingBST(root);
    printRightSkewedTree(result);
    
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI