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

23
August 2020

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.

Loading Comments...

- All Elements in Two Binary Search Trees Solution
- Construct Binary Search Tree From Preorder Traversal Solution
- Maximum Binary Tree Solution
- Sum of Nodes With Even Valued Grandparent Solution
- Deepest Leaves Sum Solution
- Symmetric Tree or Mirror Tree Solution
- Diameter of Binary Tree Solution
- Binary Tree Paths Solution
- Cousins in Binary Tree Solution
- Sum of Left Leaves Solution
- Same Tree or Equal Tree Solution
- Minimum Absolute Difference in BST Solution
- Construct String From Binary Tree Solution - Leetcode
- Two Sum IV - Input is a BST Solution - Leetcode
- Convert BST to Greater Tree Solution - Leetcode
- Convert Sorted Array to Binary Search Tree Solution
- Average of Levels in Binary Tree Solution
- Leaf Similar Trees Solution - Leetcode
- Sum of Root to Leaf Binary Numbers - Leetcode
- Univalued Binary Tree - Leetcode
- Maximum Depth of N Ary Tree - Leetcode
- Increasing Order Search Tree - Leetcode
- Merge Two Binary Trees Solution
- Range Sum of BST - Leetcode