Increasing Order Search Tree - Leetcode

Leetcode Solution: Understand and solve Leetcode problem Increasing Order Search Tree(897)

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... Disqus Loader

Increasing Order Search Tree - Leetcode

Leetcode Solution: Understand and solve Leetcode problem Increasing Order Search Tree(897)

Related Pages: