# Increasing Order Search Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/increasing-order-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/increasing-order-search-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Stack, Tree, Binary Tree, Binary Search Tree
---
## Problem
Given the `root` of a binary search tree, rearrange the tree in **in-order** so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

**Example 1:**

![](https://assets.glich.co/dsa/increasing-order-search-tree/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/increasing-order-search-tree/image1.jpg) 

**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`

# Approaches
## Using In-order Traversal and an Auxiliary List
This approach first performs a standard in-order traversal of the Binary Search Tree. During the traversal, it stores all the node values in an auxiliary list. Since it's a BST, an in-order traversal naturally yields the values in ascending order. After collecting all the values, a new tree is constructed from this sorted list. The new tree is a skewed tree where each node only has a right child.
**Time:** O(N), where N is the number of nodes in the tree. The in-order traversal takes O(N) time to visit every node. Building the new tree from the list also takes O(N) time. · **Space:** O(N), where N is the number of nodes. We use an `ArrayList` to store all N node values. Additionally, the recursion stack for the in-order traversal can go up to O(H) where H is the height of the tree. In the worst case of a skewed tree, H can be N, making the total space complexity O(N).
**Pros:** Simple to understand and implement.; Clearly separates the logic of traversal and tree construction.
**Cons:** Uses significant extra space (O(N)) for the list.; Creates entirely new nodes, which is less efficient than modifying the existing tree structure in-place.
### Explanation
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.

```java
/**
 * 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 {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);

        TreeNode dummyNode = new TreeNode(-1);
        TreeNode currentNode = dummyNode;
        for (int val : vals) {
            currentNode.right = new TreeNode(val);
            currentNode = currentNode.right;
        }
        return dummyNode.right;
    }

    private void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) {
            return;
        }
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}
```
### Algorithm
*   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.

## In-place Relinking with Recursive In-order Traversal
This approach improves upon the first one by avoiding the use of an auxiliary list to store values. Instead, it rearranges the tree pointers directly during the in-order traversal. A pointer (passed by reference or as a member variable) is used to keep track of the last visited node (the current tail of the new skewed tree), allowing the current node to be attached to it.
**Time:** O(N), as each node is visited exactly once during the in-order traversal. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the best case (a completely balanced tree), the space is O(log N). In the worst case (a skewed tree), the space is O(N).
**Pros:** More space-efficient than the list-based approach, especially for balanced trees.; It modifies the tree in-place, reusing the existing nodes and avoiding the overhead of creating new objects.
**Cons:** The use of a member variable or a global-like pointer can sometimes be considered less clean.; The space complexity is still O(N) in the worst-case scenario of a skewed tree due to recursion depth.
### Explanation
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.

```java
/**
 * 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 currentNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyRoot = new TreeNode(-1);
        currentNode = dummyRoot;
        inorder(root);
        return dummyRoot.right;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);

        // Relink the node
        node.left = null;
        currentNode.right = node;
        currentNode = node;

        inorder(node.right);
    }
}
```
### Algorithm
*   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`.

## Optimal In-place Relinking using Morris Traversal
This is the most efficient approach in terms of space complexity. It uses an iterative technique called Morris Traversal to perform an in-order traversal without using recursion or an explicit stack. This allows the tree to be relinked in-place with constant extra space. The core idea of Morris Traversal is to create temporary links (threads) to navigate the tree and then remove them after use, enabling traversal without a stack.
**Time:** O(N). Each node is visited, and each edge is traversed at most twice (once down, once up via the temporary link). The overall complexity remains linear. · **Space:** O(1). This approach uses only a few extra pointers (`dummyRoot`, `tail`, `current`, `predecessor`) regardless of the tree's size, making it the most space-efficient solution.
**Pros:** Optimal space complexity of O(1).; Modifies the tree in-place without recursion, avoiding potential stack overflow issues for very deep trees.
**Cons:** The logic is significantly more complex and harder to understand and implement correctly compared to other approaches.
### Explanation
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.

```java
/**
 * 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 {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyRoot = new TreeNode(-1);
        TreeNode tail = dummyRoot;
        TreeNode current = root;

        while (current != null) {
            if (current.left == null) {
                // Process current node
                tail.right = current;
                tail = current;
                current = current.right;
            } else {
                // Find the in-order predecessor
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // Create temporary link
                    predecessor.right = current;
                    TreeNode temp = current.left;
                    current.left = null; // Set left to null as we move down
                    current = temp;
                } else {
                    // Remove temporary link and process current node
                    predecessor.right = null;
                    // The node is already linked by the tail from the previous step
                    // when its left child was processed. We just need to move to the right.
                    tail.right = current;
                    tail = current;
                    current = current.right;
                }
            }
        }
        return dummyRoot.right;
    }
}
```
*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.*
### Algorithm
*   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`.

# Solutions
### Java

```java
/** * 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 prev ; public TreeNode increasingBST ( TreeNode root ) { TreeNode dummy = new TreeNode ( 0 , null , root ); prev = dummy ; dfs ( root ); return dummy . right ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); prev . right = root ; root . left = null ; prev = root ; dfs ( root . right ); } }
```

### CPP

```cpp
/** * 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 , nullptr , root ); TreeNode * prev = dummy ; function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return ; } dfs ( root -> left ); prev -> right = root ; root -> left = nullptr ; prev = root ; dfs ( root -> right ); }; dfs ( root ); return dummy -> right ; } };
```

### Python

```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 : TreeNode ) -> TreeNode : def dfs ( root ): if root is None : return nonlocal prev dfs ( root . left ) prev . right = root root . left = None prev = root dfs ( root . right ) dummy = prev = TreeNode ( right = root ) dfs ( root ) return dummy . right
```