@Test(expected = IllegalArgumentException.class) public void shouldNotAcceptNullBinaryNodesIterative() { binaryTreePostOrder.getIterative(null); }
public List<BinaryNode> getIterative(BinaryNode root) { validateTree(root); List<BinaryNode> result = new LinkedList<BinaryNode>(); Stack<BinaryNode> stack = new Stack<BinaryNode>(); stack.push(root); BinaryNode prev = null; while (!stack.empty()) { BinaryNode current = stack.peek(); if (prev == null || prev.getLeft() == current || prev.getRight() == current) { if (current.getLeft() != null) { stack.push(current.getLeft()); } else if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getLeft() == prev) { if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getRight() == prev) { stack.pop(); result.add(current); } prev = current; } return result; }
BinaryTreePostOrder { public List<BinaryNode> getIterative(BinaryNode root) { validateTree(root); List<BinaryNode> result = new LinkedList<BinaryNode>(); Stack<BinaryNode> stack = new Stack<BinaryNode>(); stack.push(root); BinaryNode prev = null; while (!stack.empty()) { BinaryNode current = stack.peek(); if (prev == null || prev.getLeft() == current || prev.getRight() == current) { if (current.getLeft() != null) { stack.push(current.getLeft()); } else if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getLeft() == prev) { if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getRight() == prev) { stack.pop(); result.add(current); } prev = current; } return result; } }
BinaryTreePostOrder { public List<BinaryNode> getIterative(BinaryNode root) { validateTree(root); List<BinaryNode> result = new LinkedList<BinaryNode>(); Stack<BinaryNode> stack = new Stack<BinaryNode>(); stack.push(root); BinaryNode prev = null; while (!stack.empty()) { BinaryNode current = stack.peek(); if (prev == null || prev.getLeft() == current || prev.getRight() == current) { if (current.getLeft() != null) { stack.push(current.getLeft()); } else if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getLeft() == prev) { if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getRight() == prev) { stack.pop(); result.add(current); } prev = current; } return result; }  }
BinaryTreePostOrder { public List<BinaryNode> getIterative(BinaryNode root) { validateTree(root); List<BinaryNode> result = new LinkedList<BinaryNode>(); Stack<BinaryNode> stack = new Stack<BinaryNode>(); stack.push(root); BinaryNode prev = null; while (!stack.empty()) { BinaryNode current = stack.peek(); if (prev == null || prev.getLeft() == current || prev.getRight() == current) { if (current.getLeft() != null) { stack.push(current.getLeft()); } else if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getLeft() == prev) { if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getRight() == prev) { stack.pop(); result.add(current); } prev = current; } return result; }  List<BinaryNode> getRecursive(BinaryNode root); List<BinaryNode> getIterative(BinaryNode root); }
BinaryTreePostOrder { public List<BinaryNode> getIterative(BinaryNode root) { validateTree(root); List<BinaryNode> result = new LinkedList<BinaryNode>(); Stack<BinaryNode> stack = new Stack<BinaryNode>(); stack.push(root); BinaryNode prev = null; while (!stack.empty()) { BinaryNode current = stack.peek(); if (prev == null || prev.getLeft() == current || prev.getRight() == current) { if (current.getLeft() != null) { stack.push(current.getLeft()); } else if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getLeft() == prev) { if (current.getRight() != null) { stack.push(current.getRight()); } else { stack.pop(); result.add(current); } } else if (current.getRight() == prev) { stack.pop(); result.add(current); } prev = current; } return result; }  List<BinaryNode> getRecursive(BinaryNode root); List<BinaryNode> getIterative(BinaryNode root);  }