# LeetCode 897. Increasing Order Search Tree

## Description

https://leetcode.com/problems/increasing-order-search-tree/

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:

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

## Explanation

Do an in-order traverse binary search tree to find out ascending order values first. Then create a new increasing order tree.

## Python Solution

``````# 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:
self.orders = []

self.traverse(root)
new_root = TreeNode(self.orders)

node = new_root
for val in self.orders[1:]:
node.right = TreeNode(val)
node = node.right

return new_root

def traverse(self, root):
if not root:
return

self.traverse(root.left)

self.orders.append(root.val)

self.traverse(root.right)

``````
• Time Complexity: O(N)
• Space Complexity: O(N)