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