How to traverse a binary tree? Well, recursion is the most obvious solution, which is elegant, shows beauty of algorithm, and is suitable of binary tree’s recursion nature. Now, some may want to dig into it deeper: what actually recursion does? To answer that, we need to design an algorithm to traverse a binary tree without recursion.
Let’s have a closer look into the recursion process. A recursion means a function will call itself. We know function calling is implemented based on stack. That means, for a recursive calling process, there are two order sequences:
- in-order: Caller functions step into callee functions.
- out-order: Step outside callee functions and into caller functions.
Generally, we need to simulate the two sides when traversing a binary tree without recursion. To achive this, we use different states to indicate the right order of visiting nodes of a binary tree:
- NOT: The node is not visited and firstly visit the node.
- IN: Have visited the left child of the node.
- OUT: Have visited the both children of the node.
Below is an iterative description about how to traverse a binary tree with maintaining the above states for each node.
- Prepare a stack and push the root node with state NOT
- While the stack is not empty, pop a node. If its state is
- NOT: Firstly visited the node.
a. Mark its state IN, and push the node again.
b. Push its left child with state NOT if have. - IN: Have visited the node and its left child.
a. Marks its state OUT and push the node again.
b. Push its right child with state NOT if have. - OUT: Have visited its left and right child.
a. Do nothing. (Just pop the node)
That’s it! The above algorithm captures the in-order and out-order of recursion very well. Based on it, you could do anything whatever recursion could do:
- For pre-order traverse, execute operation when meet an NOT node.
- For mid-order traverse, execute operation when meet an IN node.
- For post-order traverse, execute operation when meet an OUT node.
Let’s play it with a simple application.
Question: Given a binary search tree, print out the elements of the tree in mid-order without using recursion. The below is an example.
Here is the implentation.
