algoadvance

Leetcode 897. Increasing Order Search Tree

Problem Statement

Given the root of a binary search tree, rearrange the tree in an “in-order” manner 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:

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]

Clarifying Questions

1. Q: Will the provided tree always be a binary search tree?
   • A: Yes, the tree will always be a binary search tree.
2. Q: What should be the output format?
   • A: The output should be in the form of the tree’s in-order traversal where each node points only to a single right child.
3. Q: Can the tree be empty?
   • A: Yes, the tree can be empty. If the tree is empty, the output should also be an empty tree (or null).

Strategy

To solve this problem, we should consider the following steps:

1. In-order Traversal: Perform in-order traversal on the binary search tree to get the nodes in sorted order.
2. Reconstruction: Use the nodes obtained from the in-order traversal to construct the new tree where each node points only to its right child, and there are no left children.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    // Dummy node to act as a previous node pointer
    private TreeNode prevNode = new TreeNode(0);
    private TreeNode newRoot = prevNode;

    public TreeNode increasingBST(TreeNode root) {
        helper(root);
        return newRoot.right;
    }

    private void helper(TreeNode node) {
        if (node == null) {
            return;
        }

        // Recur on the left subtree
        helper(node.left);

        // Here `node` is the in-order fixation
        // Set left child to null
        node.left = null;

        // Set the previous node's right child
        prevNode.right = node;

        // Move to the next node
        prevNode = node;

        // Recur on the right subtree
        helper(node.right);
    }
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary search tree. This is because each node is visited exactly once during the in-order traversal.
• Space Complexity: O(H) where H is the height of the tree, due to the recursion stack. In the worst-case scenario (unbalanced tree), this can be O(N), but in the average case of a balanced tree, this would be O(log N).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?