# LeetCode: Increasing Order Search Tree C#

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

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. Constraints:

The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000.

using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
/// <summary>
/// https://leetcode.com/problems/increasing-order-search-tree/
/// </summary>
[TestClass]
public class IncreasingBstTest
{
[TestMethod]
public void ExampleTest()
{

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

TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);

root.right = new TreeNode(6);
root.right.right = new TreeNode(8);
root.right.right.left = new TreeNode(7);
root.right.right.right = new TreeNode(9);
var forEach = new InOrderForEach();
root = forEach.IncreasingBST(root);

int res = 1;
var curr = root;
while (curr != null)
{
Assert.AreEqual(res, curr.val);
curr = curr.right;
res++;
}
}
}

}

public class InOrderForEach
{
public TreeNode IncreasingBST(TreeNode root)
{
if (root == null)
{
return null;
}
List<int> vals = new List<int>();
InOrder(root, vals);
var ans = new TreeNode(0);
TreeNode curr = ans;
foreach (var v in vals)
{
curr.right = new TreeNode(v);
curr = curr.right;
}
return ans.right;
}

private void InOrder(TreeNode root, List<int> vals)
{
if (root == null)
{
return;
}
InOrder(root.left, vals);
InOrder(root.right, vals);
}

}
}


There isn't much to review. InOrder() is merely a depth-first-search, so maybe I would call it that.

You could though optimize a bit, if you created the new "tree" as you traverse the old one:

  public class InOrderForEach
{
TreeNode newRoot = new TreeNode(0);
TreeNode current = null;

public TreeNode IncreasingBST(TreeNode root)
{
if (root == null)
{
return null;
}
current = newRoot;
InOrder(root);
return newRoot.right;
}

private void InOrder(TreeNode root)
{
if (root == null)
{
return;
}
InOrder(root.left);
current = current.right = new TreeNode(root.val);
InOrder(root.right);
}

}