easy Increasing Order Search Tree

Problem Statement

Given a root node of the binary search tree, rearrange the BST in in-order such that left-most node becomes the root node of the tree, and each node has only one right child but no left child.

Examples

Example 1:

• Input: root = [2,1,4,null,null,3]

• Expected Output: [1,null,2,null,3,null,4]
• Justification: The original tree has the root at 2, with 1 as the left child and a subtree rooted at 4 with 3 as its left child. The rearranged tree starts with 1, then proceeds to 2, followed by 3, and ends with 4, each as the right child of the previous.

Example 2:

• Input: root = [3,2,5,1,null,4,6]
• Expected Output: [1,null,2,null,3,null,4,null,5,null,6]
• Justification: Starting from 1 (the smallest value), each node is connected to the next higher value as its right child until the highest value, 6, is reached.

Example 3:

• Input: root = [1,null,2,null,3,null,4,null,5]
• Expected Output: [1,null,2,null,3,null,4,null,5]
• Justification: The input tree is already a right-skewed tree representing an ascending order sequence. Therefore, the output remains the same as the input.

Solution

To solve this problem, we'll employ an in-order traversal approach, which naturally visits the nodes of a BST in ascending order. This traversal will help us rearrange the tree by ensuring that each node we visit is placed as the right child of the previously visited node. The key here is to maintain a pointer to the last node we've rearranged so we can easily append the next node in order. This approach is effective because it leverages the sorted property of BSTs and allows us to transform the tree in-place, ensuring space efficiency.

Initially, we'll start with a dummy node as a precursor to the first node in our rearranged tree, which simplifies the process of connecting the nodes. As we perform the in-order traversal, we'll continuously update the right child of the last node to point to the current node, effectively "flattening" the tree into a single rightward path. This method is the most effective because it does not require additional space for node storage, and it directly constructs the final structure during the traversal.

Step-by-step Algorithm

1. Initialize a Dummy Node: Start by creating a dummy node. This node acts as a placeholder to simplify the process of attaching nodes in increasing order. Its right child will eventually point to the smallest element in the tree, marking the beginning of our transformed tree.

2. In-Order Traversal Setup: Prepare to perform an in-order traversal of the BST. This type of traversal visits nodes in ascending order, which aligns perfectly with our goal of rearranging the tree.

3. Traversal and Transformation:

   • Visit Left: Recursively visit the left child of the current node. This step ensures that we start with the smallest element.
   • Rearrange Nodes: After visiting the left child, perform the following for the current node:
     • Detach the left child by setting currentNode.left to null. This step is crucial as we're transforming the BST into a structure where each node only has a right child.
     • Attach the current node to the right of the last node processed. This is done by setting lastNode.right to the current node.
     • Update lastNode to the current node, preparing it to attach the next node in sequence.
   • Visit Right: Recursively visit the right child of the current node to continue the in-order traversal.

4. Finalize the Transformation: After the traversal is complete, the right child of the dummy node points to the smallest element, and all subsequent elements are attached as right children in increasing order. Return dummy.right as the new root of the transformed tree.

Algorithm Walkthrough

Let's consider the input [3,2,5,1,null,4,6]

    3
   / \
  2   5
 /   / \
1   4   6

Step-by-Step Transformation:

1. Initialize Dummy Node: Create a dummy node. This node serves as a starting point for rearranging the tree.

2. Start In-Order Traversal:

   • Begin with the root node (3).

3. Visit Left Subtree of 3:

   • Move to node 2.
   • Visit left subtree of 2, which is node 1.

4. Process Node 1:

   • Node 1 has no left child, so we start the rearrangement here.
   • Detach left child (none in this case).
   • Attach node 1 to the right of the dummy node.
   • Update lastNode to node 1.

5. Back to Node 2:

   • Detach left child (previously node 1).
   • Attach node 2 to the right of node 1 (the current lastNode).
   • Update lastNode to node 2.

6. Proceed to Root Node 3:

   • Node 3's left child (node 2) has been fully processed.
   • Detach left child (node 2 is now attached to the transformed tree, not directly as a left child).
   • Attach node 3 to the right of node 2 (the current lastNode).
   • Update lastNode to node 3.

7. Visit Right Subtree of 3:

   • Move to node 5.
   • Visit left subtree of 5, which is node 4.

8. Process Node 4:

   • Node 4 has no left child.
   • Detach left child (none).
   • Attach node 4 to the right of node 3 (the current lastNode).
   • Update lastNode to node 4.

9. Back to Node 5:

   • Detach left child (node 4 is now part of the transformed tree).
   • Attach node 5 to the right of node 4.
   • Update lastNode to node 5.

10. Visit Right Subtree of 5:

    • Move to node 6.
    • Process node 6 similarly, attaching it to the right of node 5.

Final Transformed Tree:

The final tree, starting from dummy.right, follows a straight path: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Code

import java.util.LinkedList;
import java.util.Queue;

// class TreeNode {
//     int val;
//     TreeNode left, right;

//     TreeNode(int x) {
//         val = x;
//     }
// }

class Solution {

  private TreeNode lastNode = null;

  public TreeNode increasingBST(TreeNode root) {
    TreeNode dummy = new TreeNode(0); // Step 1: Create a dummy node.
    lastNode = dummy;
    inOrder(root); // Step 2: Perform in-order traversal to rearrange the tree.
    return dummy.right; // Step 3: Return the right child of the dummy node, which is the new root.
  }

  private void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left); // Visit left subtree
    // Rearrange pointers
    node.left = null; // Remove left child reference
    lastNode.right = node; // Set current node as the right child of the last node
    lastNode = node; // Update last node to current
    inOrder(node.right); // Visit right subtree
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    TreeNode root1 = new TreeNode(2);
    root1.left = new TreeNode(1);
    root1.right = new TreeNode(4);
    root1.right.left = new TreeNode(3);
    // Example 2
    TreeNode root2 = new TreeNode(3);
    root2.left = new TreeNode(2);
    root2.left.left = new TreeNode(1);
    root2.right = new TreeNode(5);
    root2.right.left = new TreeNode(4);
    root2.right.right = new TreeNode(6);
    // Example 3
    TreeNode root3 = new TreeNode(1);
    root3.right = new TreeNode(2);
    root3.right.right = new TreeNode(3);
    root3.right.right.right = new TreeNode(4);
    root3.right.right.right.right = new TreeNode(5);

    // Applying the method and printing the results for demonstration
    System.out.println("Example 1:");
    printTree(solution.increasingBST(root1));
    System.out.println("\nExample 2:");
    printTree(solution.increasingBST(root2));
    System.out.println("\nExample 3:");
    printTree(solution.increasingBST(root3));
  }

  public static void printTree(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      int levelSize = queue.size(); // Number of elements at the current level
      boolean isLastLevel = true;

      for (int i = 0; i < levelSize; i++) {
        TreeNode current = queue.poll();

        // Print the value of the current node
        System.out.print(current != null ? current.val + " " : "null ");

        // Add child nodes to the queue if they are not null
        if (current != null) {
          if (current.left != null || current.right != null) isLastLevel =
            false;
          queue.add(current.left);
          queue.add(current.right);
        }
      }
      // After finishing a level, if it's the last level, remove trailing nulls
      if (isLastLevel) {
        break;
      }
    }
  }
}

Complexity Analysis

Time Complexity

: Each node in the binary search tree (BST) is visited exactly once during the in-order traversal, where n is the number of nodes in the tree. Since we perform constant time operations for each node (reassigning pointers), the total time complexity is linear with respect to the number of nodes in the BST.

Space Complexity

: The space complexity is determined by the height of the tree due to the recursion stack during the in-order traversal, where h is the height of the BST.