Iterative Tree Traversal

This effectively implies creating a stack data structure as opposed to relying on the call stack to handle it. This can also be done with a queue.

Implementation with stack

while(!st.isEmpty()){
 
	Node* next = st.top();
	st.pop();
	
	if(next != nullptr){
	// do something
		st.push(next->right);
		st.push(next->left);
	}
}

Implementation with queue

#include <deque>  
  
using namespace std;  
  
struct Node {  
    Node* right;  
    Node* left;  
    int data;  
};  
  
void LevelPrint(Node* node)  
{  
    deque<Node*> q;  
    q.push_back(node);  
  
    while(!q.empty()) {  
        Node* next = q.front();  
        q.pop_front();  
  
        if(next != nullptr) {  
            //do something  
            q.push_back(next->left);  
            q.push_back(next->right);  
        }  
    }  
}

This implementation is particularly useful for level order or depth order traversal, as it effectively visits left to right by level of a tree.

Complexity

The time complexity of level order/depth order traversal of a tree is $$

O(n)

$$Howeverthespacecomplexityofbothstack-basedandqueue-basediterativetreetraversalsis$$

O(\log n)

$$asitisbasedontheheightofthetree.$$