using System.Data.SqlTypes;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace CodingInterview
{
[TestClass]
public class BuildBinarySearchTree
{
private BinaryTreeNode<T> BuildBinaryTreeFromSortedArray<T>(T[] input)
{
return BuildBinaryTreeFromSortedArrayInternal(input, 0, input.Length);
}
private BinaryTreeNode<T> BuildBinaryTreeFromSortedArrayInternal<T>(T[] input, int leftIndex, int rightIndex)
{
if (input == null || input.Length == 0)
{
return null;
}
if (leftIndex == rightIndex)
{
return null;
}
var centedIndex = (int)(rightIndex - leftIndex) / 2 + leftIndex;
var root = new BinaryTreeNode<T>(input[centedIndex]);
root.LeftNode = BuildBinaryTreeFromSortedArrayInternal<T>(input, leftIndex, centedIndex);
root.RightNode = BuildBinaryTreeFromSortedArrayInternal<T>(input, centedIndex + 1, rightIndex);
return root;
}
#region Unit tests
[TestMethod]
public void BuildBinaryTreeFromSortedArrayTest()
{
var input = new int[] { 1, 2, 3, 4, 5, 6, 7 };
var tree = BuildBinaryTreeFromSortedArray(input);
Assert.IsNotNull(tree);
Assert.AreEqual(4, tree.Data);
Assert.AreEqual(2, tree.LeftNode.Data);
Assert.AreEqual(1, tree.LeftNode.LeftNode.Data);
Assert.AreEqual(3, tree.LeftNode.RightNode.Data);
Assert.AreEqual(6, tree.RightNode.Data);
Assert.AreEqual(5, tree.RightNode.LeftNode.Data);
Assert.AreEqual(7, tree.RightNode.RightNode.Data);
}
[TestMethod]
public void BuildBinaryTreeFromSortedArrayEvenNumberOfItemsTest()
{
var input = new int[] { 1, 2, 3, 4, 5, 6 };
var tree = BuildBinaryTreeFromSortedArray(input);
Assert.IsNotNull(tree);
Assert.AreEqual(4, tree.Data);
Assert.AreEqual(2, tree.LeftNode.Data);
Assert.AreEqual(1, tree.LeftNode.LeftNode.Data);
Assert.AreEqual(3, tree.LeftNode.RightNode.Data);
Assert.AreEqual(6, tree.RightNode.Data);
Assert.AreEqual(5, tree.RightNode.LeftNode.Data);
}
[TestMethod]
public void BuildBinaryTreeFromSortedArrayZeroItemsTest()
{
var input = new int[] { };
var tree = BuildBinaryTreeFromSortedArray(input);
Assert.IsNull(tree);
}
[TestMethod]
public void BuildBinaryTreeFromSortedArrayOneItemTest()
{
var input = new int[] { 5 };
var tree = BuildBinaryTreeFromSortedArray(input);
Assert.IsNotNull(tree);
Assert.AreEqual(5, tree.Data);
Assert.IsNull(tree.LeftNode);
Assert.IsNull(tree.RightNode);
}
[TestMethod]
public void BuildBinaryTreeFromSortedArrayTwoItemsTest()
{
var input = new int[] { 5, 6 };
var tree = BuildBinaryTreeFromSortedArray(input);
Assert.IsNotNull(tree);
Assert.AreEqual(6, tree.Data);
Assert.AreEqual(5, tree.LeftNode.Data);
Assert.IsNull(tree.RightNode);
}
#endregion
}
}