Increasing Order Search Tree

• Initialize an empty ArrayList to store the node values.
• Define a recursive helper function, inorder(node, list), to perform the in-order traversal.
• In the inorder function:
  • Base case: If the current node is null, return.
  • Recursively traverse the left subtree: inorder(node.left, list).
  • Add the current node's value to the list: list.add(node.val).
  • Recursively traverse the right subtree: inorder(node.right, list).
• Call the inorder function starting from the root.
• After the traversal, create a new dummy TreeNode which will act as a placeholder for the head of the new tree.
• Create a pointer, currentNode, and point it to the dummy node.
• Iterate through the list of sorted values. For each value:
  • Create a new TreeNode with this value.
  • Set currentNode.right to this new node.
  • Move currentNode to its new right child (currentNode = currentNode.right).
• Finally, return dummyNode.right, which is the root of the newly formed skewed tree.

The simplest way to solve the problem is to separate the traversal from the construction. We can perform an in-order traversal to get all the nodes' values in a sorted manner and store them in a list. Then, we can iterate through this list and build a new tree structure as required, where each node is the right child of the previous one.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode increasingBST(TreeNode root) {18        List<Integer> vals = new ArrayList<>();19        inorder(root, vals);20 21        TreeNode dummyNode = new TreeNode(-1);22        TreeNode currentNode = dummyNode;23        for (int val : vals) {24            currentNode.right = new TreeNode(val);25            currentNode = currentNode.right;26        }27        return dummyNode.right;28    }29 30    private void inorder(TreeNode node, List<Integer> vals) {31        if (node == null) {32            return;33        }34        inorder(node.left, vals);35        vals.add(node.val);36        inorder(node.right, vals);37    }38}

• Initialize a TreeNode pointer, currentNode, to null. This will be used to build the new tree. We will also use a dummy node to simplify handling the new root. Let's create a dummyRoot = new TreeNode(-1) and initialize currentNode = dummyRoot.
• Define a recursive helper function, inorder(node).
• In the inorder function:
  • Base case: If the current node is null, return.
  • Recursively traverse the left subtree: inorder(node.left).
  • Relinking Step:
    • Set the current node's left child to null (node.left = null). This is required by the problem statement.
    • Attach the current node to the right of the tail of our new structure: currentNode.right = node.
    • Update the tail to be the current node: currentNode = node.
  • Recursively traverse the right subtree: inorder(node.right).
• Call the inorder function starting from the root.
• After the traversal completes, the dummyRoot.right will point to the new root of the rearranged tree. Return dummyRoot.right.

Instead of creating new nodes, we can reuse the existing nodes and just rearrange their pointers. We can perform an in-order traversal and, as we visit each node, we relink it. We need a pointer to keep track of the tail of the new list-like tree we are forming. A dummy node is helpful to easily get the head of the new tree.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private TreeNode currentNode;18 19    public TreeNode increasingBST(TreeNode root) {20        TreeNode dummyRoot = new TreeNode(-1);21        currentNode = dummyRoot;22        inorder(root);23        return dummyRoot.right;24    }25 26    private void inorder(TreeNode node) {27        if (node == null) {28            return;29        }30        inorder(node.left);31 32        // Relink the node33        node.left = null;34        currentNode.right = node;35        currentNode = node;36 37        inorder(node.right);38    }39}

• Create a dummy TreeNode, dummyRoot, to serve as the starting point for the new tree structure.
• Initialize a pointer tail = dummyRoot which will always point to the last node in the newly formed list.
• Initialize a pointer current = root to traverse the original tree.
• Loop while current is not null:
  • If current.left is null: This means we are at the next node in the in-order sequence.
    • Process current: Set its left child to null, append it to our result list by setting tail.right = current, and update the tail tail = current.
    • Move to the right child: current = current.right.
  • If current.left is not null: We need to visit the left subtree first.
    • Find the in-order predecessor of current (the rightmost node in its left subtree).
    • If predecessor.right is null: This is our first visit. Create a temporary link predecessor.right = current and move to the left subtree current = current.left.
    • If predecessor.right is current: We have returned from the left subtree. Remove the temporary link predecessor.right = null, process current as described above, and then move to the right current = current.right.
• Return dummyRoot.right.

To achieve O(1) space, we can use Morris Traversal. This iterative method modifies the tree on the fly to create temporary links, allowing us to traverse back up without a stack. As we perform the in-order traversal, we can relink the nodes.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode increasingBST(TreeNode root) {18        TreeNode dummyRoot = new TreeNode(-1);19        TreeNode tail = dummyRoot;20        TreeNode current = root;21 22        while (current != null) {23            if (current.left == null) {24                // Process current node25                tail.right = current;26                tail = current;27                current = current.right;28            } else {29                // Find the in-order predecessor30                TreeNode predecessor = current.left;31                while (predecessor.right != null && predecessor.right != current) {32                    predecessor = predecessor.right;33                }34 35                if (predecessor.right == null) {36                    // Create temporary link37                    predecessor.right = current;38                    TreeNode temp = current.left;39                    current.left = null; // Set left to null as we move down40                    current = temp;41                } else {42                    // Remove temporary link and process current node43                    predecessor.right = null;44                    // The node is already linked by the tail from the previous step45                    // when its left child was processed. We just need to move to the right.46                    tail.right = current;47                    tail = current;48                    current = current.right;49                }50            }51        }52        return dummyRoot.right;53    }54}

Note: A careful implementation of Morris Traversal is needed to correctly handle the relinking and setting left pointers to null. The key is to process (relink) a node only when its entire left subtree has been visited.