Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def inorder(node):
            if not node:
                return
            yield from inorder(node.left)
            yield node
            yield from inorder(node.right)
        
        dummy = TreeNode(0)
        curr = dummy
        for node in inorder(root):
            node.left = None
            curr.right = node
            curr = node
        return dummy.right
      

/**
 * 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) {
        TreeNode* dummy = new TreeNode(0);
        TreeNode* curr = dummy;
        inorder(root, curr);
        return dummy->right;
    }
    
    void inorder(TreeNode* node, TreeNode*& curr) {
        if (!node) return;
        inorder(node->left, curr);
        node->left = nullptr;
        curr->right = node;
        curr = node;
        inorder(node->right, curr);
    }
};
      

/**
 * 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 {
    private TreeNode curr;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        curr = dummy;
        inorder(root);
        return dummy.right;
    }
    
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        curr.right = node;
        curr = node;
        inorder(node.right);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function(root) {
    let dummy = new TreeNode(0);
    let curr = dummy;
    
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        node.left = null;
        curr.right = node;
        curr = node;
        inorder(node.right);
    }
    
    inorder(root);
    return dummy.right;
};
      

Problem Description

Given the root of a binary search tree (BST), rearrange the tree so that it becomes an increasing order search tree. In this new tree, the leftmost node of the original BST becomes the new root, and every node has no left child and only one right child. The resulting tree should look like a singly linked list in ascending order, where each node points to the next higher node via its right pointer.

• Each node's left child must be null.
• You must use the original nodes (do not create new nodes or reuse values).
• The input is guaranteed to be a valid BST.
• There is only one valid answer for each input.

Thought Process

To solve this problem, we need to transform the BST into a right-skewed tree that represents the in-order traversal of the original tree. We know that in-order traversal of a BST yields nodes in ascending order. The challenge is to rearrange the tree in-place, connecting each node's right pointer to the next node in order, and setting all left pointers to null.

A brute-force approach might be to collect all node values in a list during traversal, and then build a new tree. However, the problem requires us to reuse the original nodes, not just their values. Therefore, we need an approach that traverses the tree and rearranges pointers as we go.

The key insight is that if we traverse the BST in-order, we can keep track of the "current" node we are building the new tree from, and for each visited node, set its left to null and attach it to the right of the current node.

Solution Approach

The solution uses in-order traversal to visit nodes in ascending order and rearrange their pointers to form the desired increasing order search tree. Here is the step-by-step approach:

1. Initialize a dummy node: Create a dummy node to serve as the starting point of the new tree. This helps in easily attaching the first real node without special cases.
2. Use a current pointer: Maintain a pointer (curr) that always points to the last node added to the new tree.
3. In-order traversal: Traverse the original BST in in-order fashion (left, node, right). For each visited node:
   • Set its left child to null (since the new tree has no left children).
   • Attach the node to the right of curr.
   • Move curr to this node.
4. Return the new root: After traversal, the right child of the dummy node is the new root of the rearranged tree.

This approach leverages the properties of BST and in-order traversal, and efficiently rearranges the original nodes without creating new ones.

Example Walkthrough

Consider the following BST:

        5
       / \
      3   6
     / \   \
    2   4   8
   /       / \
  1       7   9
  

The in-order traversal of this tree yields: 1, 2, 3, 4, 5, 6, 7, 8, 9.

• We start with a dummy node and a curr pointer.
• We visit node 1: Set its left to null, attach to curr.right, move curr to 1.
• Visit node 2: Set left to null, attach to curr.right (1->2), move curr to 2.
• Continue for 3, 4, 5, ... up to 9.
• The final tree is: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 (all using right pointers, left pointers are null).

At each step, we are reusing the original nodes and rearranging their pointers as required.

Time and Space Complexity

• Brute-force approach:
  • Collect all node values in a list (O(N)), then build a new tree (O(N)).
  • Space: O(N) for the list and new nodes.
• Optimized in-place approach (used here):
  • Time Complexity: O(N), where N is the number of nodes, since each node is visited once during in-order traversal.
  • Space Complexity: O(H), where H is the height of the tree, for the recursion stack (O(log N) for balanced BST, O(N) for skewed).
  • No extra space for node storage, since we reuse the original nodes.

Summary

The Increasing Order Search Tree problem is elegantly solved by leveraging the in-order traversal property of BSTs, which yields nodes in ascending order. By maintaining a dummy node and rearranging pointers during traversal, we efficiently transform the BST into a right-skewed tree without creating new nodes. This approach is both time and space efficient, and highlights the power of recursive tree traversal and pointer manipulation in solving tree restructuring problems.