document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. using System.Data.SqlTypes;
  2. using Microsoft.VisualStudio.TestTools.UnitTesting;
  3.  
  4. namespace CodingInterview
  5. {
  6.     [TestClass]
  7.     public class BuildBinarySearchTree
  8.     {
  9.         private BinaryTreeNode<T> BuildBinaryTreeFromSortedArray<T>(T[] input)
  10.         {
  11.             return BuildBinaryTreeFromSortedArrayInternal(input, 0, input.Length);
  12.         }
  13.         private BinaryTreeNode<T> BuildBinaryTreeFromSortedArrayInternal<T>(T[] input, int leftIndex, int rightIndex)
  14.         {
  15.             if (input == null || input.Length == 0)
  16.             {
  17.                 return null;
  18.             }
  19.  
  20.             if (leftIndex == rightIndex)
  21.             {
  22.                 return null;
  23.             }
  24.  
  25.             var centedIndex = (int)(rightIndex - leftIndex) / 2 + leftIndex;
  26.             var root = new BinaryTreeNode<T>(input[centedIndex]);
  27.             root.LeftNode = BuildBinaryTreeFromSortedArrayInternal<T>(input, leftIndex, centedIndex);
  28.             root.RightNode = BuildBinaryTreeFromSortedArrayInternal<T>(input, centedIndex + 1, rightIndex);
  29.  
  30.             return root;
  31.         }
  32.  
  33.         #region Unit tests
  34.         [TestMethod]
  35.         public void BuildBinaryTreeFromSortedArrayTest()
  36.         {
  37.             var input = new int[] { 1, 2, 3, 4, 5, 6, 7 };
  38.  
  39.             var tree = BuildBinaryTreeFromSortedArray(input);
  40.  
  41.             Assert.IsNotNull(tree);
  42.  
  43.             Assert.AreEqual(4, tree.Data);
  44.             Assert.AreEqual(2, tree.LeftNode.Data);
  45.             Assert.AreEqual(1, tree.LeftNode.LeftNode.Data);
  46.             Assert.AreEqual(3, tree.LeftNode.RightNode.Data);
  47.             Assert.AreEqual(6, tree.RightNode.Data);
  48.             Assert.AreEqual(5, tree.RightNode.LeftNode.Data);
  49.             Assert.AreEqual(7, tree.RightNode.RightNode.Data);
  50.         }
  51.  
  52.         [TestMethod]
  53.         public void BuildBinaryTreeFromSortedArrayEvenNumberOfItemsTest()
  54.         {
  55.             var input = new int[] { 1, 2, 3, 4, 5, 6 };
  56.  
  57.             var tree = BuildBinaryTreeFromSortedArray(input);
  58.  
  59.             Assert.IsNotNull(tree);
  60.  
  61.             Assert.AreEqual(4, tree.Data);
  62.             Assert.AreEqual(2, tree.LeftNode.Data);
  63.             Assert.AreEqual(1, tree.LeftNode.LeftNode.Data);
  64.             Assert.AreEqual(3, tree.LeftNode.RightNode.Data);
  65.             Assert.AreEqual(6, tree.RightNode.Data);
  66.             Assert.AreEqual(5, tree.RightNode.LeftNode.Data);
  67.         }
  68.  
  69.         [TestMethod]
  70.         public void BuildBinaryTreeFromSortedArrayZeroItemsTest()
  71.         {
  72.             var input = new int[] { };
  73.  
  74.             var tree = BuildBinaryTreeFromSortedArray(input);
  75.  
  76.             Assert.IsNull(tree);
  77.         }
  78.  
  79.         [TestMethod]
  80.         public void BuildBinaryTreeFromSortedArrayOneItemTest()
  81.         {
  82.             var input = new int[] { 5 };
  83.  
  84.             var tree = BuildBinaryTreeFromSortedArray(input);
  85.  
  86.             Assert.IsNotNull(tree);
  87.             Assert.AreEqual(5, tree.Data);
  88.             Assert.IsNull(tree.LeftNode);
  89.             Assert.IsNull(tree.RightNode);
  90.         }
  91.  
  92.         [TestMethod]
  93.         public void BuildBinaryTreeFromSortedArrayTwoItemsTest()
  94.         {
  95.             var input = new int[] { 5, 6 };
  96.  
  97.             var tree = BuildBinaryTreeFromSortedArray(input);
  98.  
  99.             Assert.IsNotNull(tree);
  100.             Assert.AreEqual(6, tree.Data);
  101.             Assert.AreEqual(5, tree.LeftNode.Data);
  102.             Assert.IsNull(tree.RightNode);
  103.         }
  104.  
  105.         #endregion
  106.     }
  107. }
');