Increasing Order Search Tree

Problem Statement

The task is to modify a binary search tree (BST) by rearranging its nodes so it forms a right-skewed tree. Each node in this modified tree should have no left child and only one right child, starting from the leftmost node of the original BST. This transformation requires a traversal of the nodes in their in-order sequence to recreate the tree appropriately, ensuring that the smallest node becomes the root and leading upwards sequentially.

Examples

Example 1

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]

Example 2

Input:

root = [5,1,7]

Output:

[1,null,5,null,7]

Constraints

• The number of nodes in the given tree will be in the range [1, 100].
• 0 <= Node.val <= 1000

Approach and Intuition

The key to solving this problem lies in understanding the properties of the BST and the in-order traversal method:

1. First, perform an in-order traversal of the BST. This traversal will access the nodes in ascending order due to the properties of the BST where:

   • Left subtree nodes < Root
   • Right subtree nodes > Root

2. During the traversal, store the nodes in a temporary list as they appear.

3. Once all nodes are accessed and stored, reconstruct the BST from this list:

   • Take the first element in the list as the root.
   • Iterate through the rest and for each node, set it as the right child of the previous node so that no left children exist.

This streamlined approach leverages the in-order traversal which naturally aligns with the requirement of creating a singly-linked right-skewed "tree", which visually will resemble a linked list more than a traditional binary tree.

Solutions

class Solution {    
    public TreeNode rearrangeTree(TreeNode root) {
        List<Integer> values = new ArrayList();
        collectInOrder(root, values);
        TreeNode newRoot = new TreeNode(0), current = newRoot;
        for (int value: values) {
            current.right = new TreeNode(value);
            current = current.right;
        }
        return newRoot.right;
    }
    
    public void collectInOrder(TreeNode node, List<Integer> values) {
        if (node == null) return;
        collectInOrder(node.left, values);
        values.add(node.val);
        collectInOrder(node.right, values);
    }
}