BinaryTreeByLevel { public List<BinaryNode> getWithoutAdditionalDataStructures(BinaryNode root) { validateBinaryNode(root); List<BinaryNode> result = new LinkedList<BinaryNode>(); int depth = getDepth(root); for (int i = 1; i <= depth; i++) { result.addAll(getNodesForLevel(root, i)); } return result; }  List<BinaryNode> getUsingQueue(BinaryNode root); List<BinaryNode> getWithoutAdditionalDataStructures(BinaryNode root);  }
@Test(expected = IllegalArgumentException.class) public void shouldNotAcceptNullBinaryNodesWithoutExtraDataStructure() { binaryTreeByLevel.getWithoutAdditionalDataStructures(null); }
@Test public void shouldReturnTheSameNodeInTheListIfTheTreeJustContainsOneElementWithoutExtraDataStructure() { BinaryNode<Integer> root = new BinaryNode<Integer>(0); List<BinaryNode> result = binaryTreeByLevel.getWithoutAdditionalDataStructures(root); List<BinaryNode<Integer>> expectedList = Arrays.asList(root); assertEquals(expectedList, result); }
@Test public void shouldWorkWithALittleBinaryTreeWithoutExtraDataStructure() { BinaryNode<Integer> root = new BinaryNode<Integer>(0); BinaryNode<Integer> n1 = new BinaryNode<Integer>(1); BinaryNode<Integer> n2 = new BinaryNode<Integer>(2); root.setLeft(n1); root.setRight(n2); List<BinaryNode> result = binaryTreeByLevel.getWithoutAdditionalDataStructures(root); List<BinaryNode<Integer>> expectedList = Arrays.asList(root, n1, n2); assertEquals(expectedList, result); }
@Test public void shouldWorkWithABiggerBinaryTreeWithoutExtraDataStructure() { BinaryNode<Integer> root = new BinaryNode<Integer>(0); BinaryNode<Integer> n1 = new BinaryNode<Integer>(1); BinaryNode<Integer> n2 = new BinaryNode<Integer>(2); BinaryNode<Integer> n3 = new BinaryNode<Integer>(3); BinaryNode<Integer> n4 = new BinaryNode<Integer>(4); BinaryNode<Integer> n5 = new BinaryNode<Integer>(5); root.setLeft(n1); root.setRight(n2); n1.setLeft(n3); n1.setRight(n4); n2.setLeft(n5); List<BinaryNode> result = binaryTreeByLevel.getWithoutAdditionalDataStructures(root); List<BinaryNode<Integer>> expectedList = Arrays.asList(root, n1, n2, n3, n4, n5); assertEquals(expectedList, result); }