This function traverses a binary tree iteratively using the in-order tree-traversal algorithm. The Traversal should not use recursion.
tree = 1 / \ 2 3 / / \ 4 6 7 \ 9
// The input callback will have been called in the following order: callback(4) callback(9) callback(2) callback(1) callback(6) callback(3) callback(7)
# O(n) time | O(1) space DEFINE FUNCTION iterativeInOrderTraversal(tree, callback): SET previousNode TO None SET currentNode TO tree WHILE currentNode is not None: IF previousNode is None or previousNode EQUALS currentNode.parent: IF currentNode.left is not None: SET nextNode TO currentNode.left ELSE: callback(currentNode) SET nextNode TO currentNode.right IF currentNode.right is not None else currentNode.parent ELSEIF previousNode EQUALS currentNode.left: callback(currentNode) SET nextNode TO currentNode.right IF currentNode.right is not None else currentNode.parent ELSE: SET nextNode TO currentNode.parent SET previousNode TO currentNode SET currentNode TO nextNode