BinaryTreeInOrder { public List<BinaryNode<Integer>> getIterative(BinaryNode<Integer> root) { validateBinaryNode(root); List<BinaryNode<Integer>> result = new LinkedList<BinaryNode<Integer>>(); Stack<BinaryNode> stack = new Stack<BinaryNode>(); BinaryNode current = root; while (!stack.empty() || current != null) { if (current != null) { stack.push(current); current = current.getLeft(); } else { BinaryNode node = stack.pop(); result.add(node); current = node.getRight(); } } return result; }  List<BinaryNode<Integer>> getRecursive(BinaryNode root); List<BinaryNode<Integer>> getIterative(BinaryNode<Integer> root);  }
@Test(expected = IllegalArgumentException.class) public void shouldNotAcceptNullBinaryNodesIterative() { binaryTreeInOrder.getIterative(null); }
@Test public void shouldReturnJustOneElementIfTheTreeContainsJustOneElementIterative() { BinaryNode<Integer> root = new BinaryNode<Integer>(0); List<BinaryNode<Integer>> result = binaryTreeInOrder.getIterative(root); List<BinaryNode<Integer>> expected = Arrays.asList(root); assertEquals(expected, result); }
@Test public void shouldReturnBinaryNodesInPreOrderIterative() { 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); root.setLeft(n1); root.setRight(n2); n1.setLeft(n3); n1.setRight(n4); List<BinaryNode<Integer>> result = binaryTreeInOrder.getIterative(root); List<BinaryNode<Integer>> expected = Arrays.asList(n3, n1, n4, root, n2); assertEquals(expected, result); }