@Test public void testIterativeInorder() { assertInorder(iterativeInorder(root)); }
public static <E> List<E> iterativeInorder(BinaryTreeNode<E> root) { BinaryTreeNode<E> current = root; BinaryTreeNode<E> previous = null; List<E> visited = new ArrayList<>(); while (current != null) { if (previous == current.parent()) { LOGGER.debug("(p = c.parent) Previous {} is parent of current {}.", previous, current); LOGGER.debug("(p = c.parent) Setting previous {} to current {}.", previous, current); previous = current; if (current.leftChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> left {}.", current, current.leftChild()); current = current.leftChild(); } else { LOGGER.debug("(p = c.parent) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.parent) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } } else if (previous == current.leftChild()) { LOGGER.debug("(p = c.left) Previous {} is left child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); previous = current; LOGGER.debug("(p = c.left) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.left) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.left) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } else if (previous == current.rightChild()) { LOGGER.debug("(p = c.right) Previous {} is right child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); LOGGER.debug("(p = c.right) Setting current {} to current -> parent {}.", current, current.parent()); previous = current; current = current.parent(); } } return visited; }
BinaryTreeWalker { public static <E> List<E> iterativeInorder(BinaryTreeNode<E> root) { BinaryTreeNode<E> current = root; BinaryTreeNode<E> previous = null; List<E> visited = new ArrayList<>(); while (current != null) { if (previous == current.parent()) { LOGGER.debug("(p = c.parent) Previous {} is parent of current {}.", previous, current); LOGGER.debug("(p = c.parent) Setting previous {} to current {}.", previous, current); previous = current; if (current.leftChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> left {}.", current, current.leftChild()); current = current.leftChild(); } else { LOGGER.debug("(p = c.parent) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.parent) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } } else if (previous == current.leftChild()) { LOGGER.debug("(p = c.left) Previous {} is left child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); previous = current; LOGGER.debug("(p = c.left) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.left) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.left) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } else if (previous == current.rightChild()) { LOGGER.debug("(p = c.right) Previous {} is right child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); LOGGER.debug("(p = c.right) Setting current {} to current -> parent {}.", current, current.parent()); previous = current; current = current.parent(); } } return visited; } }
BinaryTreeWalker { public static <E> List<E> iterativeInorder(BinaryTreeNode<E> root) { BinaryTreeNode<E> current = root; BinaryTreeNode<E> previous = null; List<E> visited = new ArrayList<>(); while (current != null) { if (previous == current.parent()) { LOGGER.debug("(p = c.parent) Previous {} is parent of current {}.", previous, current); LOGGER.debug("(p = c.parent) Setting previous {} to current {}.", previous, current); previous = current; if (current.leftChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> left {}.", current, current.leftChild()); current = current.leftChild(); } else { LOGGER.debug("(p = c.parent) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.parent) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } } else if (previous == current.leftChild()) { LOGGER.debug("(p = c.left) Previous {} is left child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); previous = current; LOGGER.debug("(p = c.left) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.left) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.left) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } else if (previous == current.rightChild()) { LOGGER.debug("(p = c.right) Previous {} is right child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); LOGGER.debug("(p = c.right) Setting current {} to current -> parent {}.", current, current.parent()); previous = current; current = current.parent(); } } return visited; }  }
BinaryTreeWalker { public static <E> List<E> iterativeInorder(BinaryTreeNode<E> root) { BinaryTreeNode<E> current = root; BinaryTreeNode<E> previous = null; List<E> visited = new ArrayList<>(); while (current != null) { if (previous == current.parent()) { LOGGER.debug("(p = c.parent) Previous {} is parent of current {}.", previous, current); LOGGER.debug("(p = c.parent) Setting previous {} to current {}.", previous, current); previous = current; if (current.leftChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> left {}.", current, current.leftChild()); current = current.leftChild(); } else { LOGGER.debug("(p = c.parent) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.parent) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } } else if (previous == current.leftChild()) { LOGGER.debug("(p = c.left) Previous {} is left child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); previous = current; LOGGER.debug("(p = c.left) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.left) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.left) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } else if (previous == current.rightChild()) { LOGGER.debug("(p = c.right) Previous {} is right child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); LOGGER.debug("(p = c.right) Setting current {} to current -> parent {}.", current, current.parent()); previous = current; current = current.parent(); } } return visited; }  static List<E> iterativeInorder(BinaryTreeNode<E> root); static List<E> recursiveInorder(BinaryTreeNode<E> root); }
BinaryTreeWalker { public static <E> List<E> iterativeInorder(BinaryTreeNode<E> root) { BinaryTreeNode<E> current = root; BinaryTreeNode<E> previous = null; List<E> visited = new ArrayList<>(); while (current != null) { if (previous == current.parent()) { LOGGER.debug("(p = c.parent) Previous {} is parent of current {}.", previous, current); LOGGER.debug("(p = c.parent) Setting previous {} to current {}.", previous, current); previous = current; if (current.leftChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> left {}.", current, current.leftChild()); current = current.leftChild(); } else { LOGGER.debug("(p = c.parent) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.parent) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.parent) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } } else if (previous == current.leftChild()) { LOGGER.debug("(p = c.left) Previous {} is left child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); previous = current; LOGGER.debug("(p = c.left) Added current {} to visited.", current); visited.add(current.data()); if (current.rightChild() != null) { LOGGER.debug("(p = c.left) Setting current {} to current -> right {}.", current, current.rightChild()); current = current.rightChild(); } else { LOGGER.debug("(p = c.left) Setting current {} to current -> parent {}.", current, current.parent()); current = current.parent(); } } else if (previous == current.rightChild()) { LOGGER.debug("(p = c.right) Previous {} is right child of current {}.", previous, current); LOGGER.debug("(p = c.left) Setting previous {} to current {}.", previous, current); LOGGER.debug("(p = c.right) Setting current {} to current -> parent {}.", current, current.parent()); previous = current; current = current.parent(); } } return visited; }  static List<E> iterativeInorder(BinaryTreeNode<E> root); static List<E> recursiveInorder(BinaryTreeNode<E> root); static final Logger LOGGER; }