##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/897.html

# 897. Increasing Order Search Tree (Easy)

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

Related Topics:
Tree, Depth-first Search, Recursion

## Solution 1. In-order Traversal

// OJ: https://leetcode.com/problems/increasing-order-search-tree
// Time: O(N)
// Space: O(H)
class Solution {
private:
TreeNode *prev;
void inorder(TreeNode *root) {
if (!root) return;
inorder(root->left);
root->left = NULL;
prev->right = root;
prev = root;
inorder(root->right);
}
public:
TreeNode* increasingBST(TreeNode* root) {
inorder(root);
}
};


## Solution 2. Post-order Traversal

// OJ: https://leetcode.com/problems/increasing-order-search-tree/
// Time: O(N)
// Space: O(H)
class Solution {
pair<TreeNode*, TreeNode*> dfs(TreeNode* root) {
TreeNode *head = root, *tail = root;
if (root->left) {
leftTail->right = root;
root->left = NULL;
}
if (root->right) {
tail = rightTail;
}
}
public:
TreeNode* increasingBST(TreeNode* root) {
return dfs(root).first;
}
};

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode increasingBST(TreeNode root) {
if (root == null || root.left == null && root.right == null)
return root;
List<Integer> inorderTraversal = inorderTraversal(root);
TreeNode newRoot = new TreeNode(inorderTraversal.get(0));
TreeNode temp = newRoot;
int size = inorderTraversal.size();
for (int i = 1; i < size; i++) {
TreeNode node = new TreeNode(inorderTraversal.get(i));
temp.right = node;
temp = temp.right;
}
return newRoot;
}

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorderTraversal = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
TreeNode visitNode = stack.pop();
node = visitNode.right;
}
return inorderTraversal;
}
}

############

/**
* 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);
}
}

• // OJ: https://leetcode.com/problems/increasing-order-search-tree
// Time: O(N)
// Space: O(H)
class Solution {
TreeNode *prev = nullptr;
public:
TreeNode* increasingBST(TreeNode* root) {
if (!root) return nullptr;
root->left = nullptr;
if (prev) prev->right = root;
prev = root;
root->right = increasingBST(root->right);
}
};

• # 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 = TreeNode(val=0, right=root)
prev = dummy
dfs(root)
return dummy.right

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def increasingBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
array = self.inOrder(root)
if not array:
return None
newRoot = TreeNode(array[0])
curr = newRoot
for i in range(1, len(array)):
curr.right =TreeNode(array[i])
curr = curr.right
return newRoot

def inOrder(self, root):
if not root:
return []
array = []
array.extend(self.inOrder(root.left))
array.append(root.val)
array.extend(self.inOrder(root.right))
return array

• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func increasingBST(root *TreeNode) *TreeNode {
dummy := &TreeNode{Val: 0, Right: root}
prev := dummy
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
prev.Right = root
root.Left = nil
prev = root
dfs(root.Right)
}
dfs(root)
return dummy.Right
}