Codiwan.com

The blog for Design Patterns, Linux, HA and Myself!

In this article we’ll be solving the problem: Increasing Order Search Tree. This problem belongs to Tree Traversal category and just like the problem, Range Sum of BST, and Merge Two Binary Trees this problem also requires a slight modification in a simple Tree Traversal approach.

```		```

Given 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 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

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

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

```
```

We’ll be using the following tree as the input to solve the problem:

As the problem description suggests, the solution requires an In Order tree traversal. If we perform an In Order tree traversal, we will get the following result.

To solve this question, we’ve to basically convert the output of the in order tree traversal to a skewed binary tree in which the 2nd element will become the right child of the 1st element and so on…

Here is the code to solve this problem which can be found here @ GitHub as well.

``````type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

var dummyRoot *TreeNode

func increasingBST(root *TreeNode) *TreeNode {
dummyRoot = &TreeNode{}
root := dummyRoot
inOrder(root)
return currentValue.Right
}

func inOrder(root *TreeNode) {
if root.Left != nil {
inOrder(root.Left)
}
dummyRoot.Right = &TreeNode{
Val:  root.Val,
}
dummyRoot = dummyRoot.Right
if root.Right != nil {
inOrder(root.Right)
}
}
``````

The function `increasingBST` calls the `inOrder` function. The `inOrder` function travers the tree and keeps on adding each of the nodes as the right child of the previously found node. Before calling `inOrder`, `increasingBST` keeps a reference of the actual root and that reference is returned after `inOrder` is complete.