Iterative Implementation for Tree Traversal

Zhao Wang

Tree traversal is a very crucial concept in data structure and algorithm, and it is also a hot point in interview. According to the order the tree nodes to be visited, it can be categorized as PreOrder, InOrder and PostOrder. These different order traversals can be easily implemented in recursion, but for iterative implementation, something is different. A stack is always needed as an auxiliary tool to store tree nodes.

Preorder Traversal

The order is: root->left->right. It is the easiest one among these three iterative implementations because we don’t need any other variables to track something. For every node popped from stack, put their non-NULL children into stack(first right then left), until the stack is empty.

Inorder Traversal

The order is: left -> root -> right. Similar to the preorder traversal, but don’t pop node out from stack first. Keep putting the left children of stack’s top node into, until there’s no…

View original post 92 more words