# LeetCode 897: Increasing Order Search Tree

## Problem Restatement

We are given the `root` of a binary search tree.

We need to rearrange the tree in inorder order so that:

| Requirement | Meaning |
|---|---|
| New root | The leftmost node of the original tree |
| Left child | Every node must have no left child |
| Right child | Each node may have one right child |
| Order | Nodes appear in increasing order |

The result should be a right-skewed tree, like a sorted linked list using only `right` pointers. The official problem states that every node should have no left child and only one right child.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root of a binary search tree |
| Output | Root of the rearranged increasing order tree |
| Tree type | Binary search tree |
| Node values | Rearranged in increasing order |
| Left pointers | Must all become `None` |

Function shape:

```python
def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    ...
```

## Examples

Example 1:

```text
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]
```

The original tree is:

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

The result is:

```text
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                9
```

Example 2:

```text
Input:  root = [5,1,7]
Output: [1,null,5,null,7]
```

The inorder order is:

```text
1, 5, 7
```

So the result is a right-only chain:

```text
1 -> 5 -> 7
```

## First Thought: Store Values, Then Rebuild

A simple approach is:

1. Run inorder traversal.
2. Store all node values in a list.
3. Build a new right-skewed tree from the sorted values.

Because the input is a binary search tree, inorder traversal visits values in increasing order.

Code idea:

```python
class Solution:
    def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        values = []

        def inorder(node):
            if not node:
                return

            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)

        dummy = TreeNode(0)
        curr = dummy

        for value in values:
            curr.right = TreeNode(value)
            curr = curr.right

        return dummy.right
```

This works, but it creates new nodes and stores all values.

We can rearrange the existing nodes directly.

## Key Insight

A binary search tree's inorder traversal visits nodes in increasing order.

So while doing inorder traversal, we can connect each visited node to the previous visited node:

```text
previous.right = current
current.left = None
```

We use a dummy node before the first real node.

The dummy node makes it easy to attach the first visited node without special handling.

## Algorithm

Create:

```python
dummy = TreeNode(0)
prev = dummy
```

Run inorder traversal.

When visiting a node:

1. Visit the left subtree first.
2. Attach the current node after `prev`.
3. Set `node.left = None`.
4. Move `prev` to the current node.
5. Visit the right subtree.

At the end, return:

```python
dummy.right
```

This is the smallest node in the original tree.

## Walkthrough

Use:

```text
root = [5,1,7]
```

Inorder traversal visits:

```text
1, 5, 7
```

Start:

```text
dummy -> None
prev = dummy
```

Visit `1`:

```text
dummy.right = 1
1.left = None
prev = 1
```

Visit `5`:

```text
1.right = 5
5.left = None
prev = 5
```

Visit `7`:

```text
5.right = 7
7.left = None
prev = 7
```

Return:

```text
dummy.right
```

which is node `1`.

The final tree is:

```text
1 -> 5 -> 7
```

using only right pointers.

## Correctness

Because the input tree is a binary search tree, inorder traversal visits its nodes in strictly increasing sorted order.

The algorithm processes nodes exactly in that inorder sequence.

Whenever it visits a node, it attaches that node as the right child of the previously visited node. Therefore, the right pointers in the output follow the inorder sequence.

The algorithm also sets each visited node's left child to `None`, so no node in the output has a left child.

The dummy node's right child is set to the first inorder node, which is the smallest node in the original tree. Therefore, the returned root is the required leftmost node.

Every original node is visited once and attached once, so the output contains exactly all original nodes in increasing order.

Thus, the algorithm returns the required increasing order search tree.

## Complexity

Let:

```text
n = number of nodes
h = height of the tree
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | Recursion stack depth is the tree height |

For a balanced tree, `h = O(log n)`. For a skewed tree, `h = O(n)`.

## Implementation

```python
# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        dummy = TreeNode(0)
        prev = dummy

        def inorder(node: Optional[TreeNode]) -> None:
            nonlocal prev

            if not node:
                return

            inorder(node.left)

            prev.right = node
            node.left = None
            prev = node

            inorder(node.right)

        inorder(root)

        return dummy.right
```

## Code Explanation

We create a dummy node:

```python
dummy = TreeNode(0)
prev = dummy
```

`prev` always points to the last node added to the new right-only tree.

The traversal is inorder:

```python
inorder(node.left)
```

This visits smaller nodes first.

When we visit the current node, we attach it after `prev`:

```python
prev.right = node
```

Then we remove its left child:

```python
node.left = None
```

This is required because the output tree must have no left children.

Now the current node becomes the last node in the chain:

```python
prev = node
```

Then we visit the right subtree:

```python
inorder(node.right)
```

At the end, the dummy node's right child is the new root:

```python
return dummy.right
```

## Tail-Recursive Style Alternative

Another elegant version passes a `tail` node.

It returns the head of the rearranged subtree, and connects the largest node of the subtree to `tail`.

```python
class Solution:
    def increasingBST(
        self,
        root: Optional[TreeNode],
        tail: Optional[TreeNode] = None
    ) -> Optional[TreeNode]:
        if not root:
            return tail

        result = self.increasingBST(root.left, root)

        root.left = None
        root.right = self.increasingBST(root.right, tail)

        return result
```

This version also rearranges the original nodes in place.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def to_right_chain(root):
    values = []

    while root:
        assert root.left is None
        values.append(root.val)
        root = root.right

    return values

def run_tests():
    s = Solution()

    root = TreeNode(
        5,
        TreeNode(1),
        TreeNode(7)
    )
    ans = s.increasingBST(root)
    assert to_right_chain(ans) == [1, 5, 7]

    root = TreeNode(
        5,
        TreeNode(
            3,
            TreeNode(2, TreeNode(1)),
            TreeNode(4)
        ),
        TreeNode(
            6,
            None,
            TreeNode(8, TreeNode(7), TreeNode(9))
        )
    )
    ans = s.increasingBST(root)
    assert to_right_chain(ans) == [1, 2, 3, 4, 5, 6, 7, 8, 9]

    root = TreeNode(1)
    ans = s.increasingBST(root)
    assert to_right_chain(ans) == [1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[5,1,7]` | Small BST example |
| Larger BST | Checks full inorder chain |
| Single node | Minimum tree |
| `left is None` assertion | Confirms output has no left children |