Recursive Tree Traversal

Pre-Order Recursive

We first print the data then traverse the left subtree and the right subtree.

In-Order Recursive

We first traverse the left subtree then print the data and then traverse right subtree.

Post-Order

We first traverse the left and right subtree then print the data.

#include<bits/stdc++.h>
using namespace std;

struct Node{
	int data;
  	Node* left;
  	Node* right;
  	Node(int data){
    	this->data = data;
      	left = right = NULL;
    }
};

void recursiveTraversal(Node* root){
	if(root == NULL) return;
  	
  	cout<<root->data<<" "; //Pre-order
  	recursiveTraversal(root->left);
  	//cout<<root->data<<" ";	//In-order	
  	recursiveTraversal(root->right);
  	//cout<<root->data<<" "; //Post-order
}

int main() {
/*
         1
       /    \
      2      3
    /   \   /  \
   4     5 6    7
*/
    struct Node* root = new Node(1);
  	root->left = new Node(2);
  	root->left->left = new Node(4);
  	root->left->right = new Node(5);
  	root->right = new Node(3);
  	root->right->left = new Node(6);
  	root->right->right = new Node(7);
    recursiveTraversal(root);
    return 0;
}

Iterative Tree Traversal

Using map and stack

For iterative traversal, we will take an unordered map and a stack. We will push the nodes to stack one by one and maintain their current state in an unordered map.

There will be three states of a node, its left part, it’s right part, and its data i.e. LRD.

We just need to do a small modification similar to recursive code to achieve inorder, preorder, and postorder iterative traversal.

#include<bits/stdc++.h>
using namespace std;

struct Node{
	int data;
  	Node* left;
  	Node* right;
  	Node(int data){
    	this->data = data;
      	left = right = NULL;
    }
};

unordered_map<Node*, int> cnt;
void iterativeTraversal(Node* root){
	if(root == NULL) return;
  	stack<Node*> s;
  	s.push(root);
  	while(!s.empty()){
        Node* cur = s.top();
        if(cur == NULL) { 
          s.pop(); 
          continue; 
        }
        
      /*Pre-Order Iterative	
      	if (cnt[cur] == 0) cout << cur->data << " " ;
        else if (cnt[cur] == 1) s.push(cur->left);
        else if (cnt[cur] == 2) s.push(cur->right);
        else s.pop();
      */
      
      /*In-Order Iterative
        if (cnt[cur] == 0) s.push(cur->left);
        else if (cnt[cur] == 1) cout << cur->data << " " ;
        else if (cnt[cur] == 2) s.push(cur->right);
        else s.pop();
      */
      
      /* Post-Order Iterative */
      	if (cnt[cur] == 0) s.push(cur->left);
        else if (cnt[cur] == 1) s.push(cur->right);
        else if (cnt[cur] == 2) cout << cur->data << " " ;
        else s.pop();
      	
      	cnt[cur]++;
    }
}

int main() {
/*
         1
       /    \
      2      3
    /   \   /  \
   4     5 6    7
*/
    struct Node* root = new Node(1);
  	root->left = new Node(2);
  	root->left->left = new Node(4);
  	root->left->right = new Node(5);
  	root->right = new Node(3);
  	root->right->left = new Node(6);
  	root->right->right = new Node(7);
    iterativeTraversal(root);
    return 0;
}

Using stack and pair

We can also reduce the extra space used by map by using a stack of pairs. In pair, we will keep Node and its current state.

#include<bits/stdc++.h>
using namespace std;

struct Node{
	int data;
  	Node* left;
  	Node* right;
  	Node(int data){
    	this->data = data;
      	left = right = NULL;
    }
};

void iterativeTraversal(Node* root){
	if(root == NULL) return;
  	stack<pair<Node*,int>> s;
  	s.push({root,0});
  	while(!s.empty()){
        Node* cur = s.top().first;
      	int state = s.top().second;
        s.pop();
        
      	if(cur == NULL || state >= 3) { 
          continue; 
        }
        
      	s.push({cur, state+1});
      	
      /*Pre-Order Iterative	
      	if (state == 0) cout << cur->data << " " ;
        else if (state == 1) s.push({cur->left, 0});
        else if (state == 2) s.push({cur->right, 0});
      */
      
      /*In-Order Iterative
      	if (state == 0) s.push({cur->left, 0});
        else if (state == 1) cout << cur->data << " " ;
        else if (state == 2) s.push({cur->right, 0});
      */
      
      /* Post-Order Iterative */
      	if (state == 0) s.push({cur->left, 0});
        else if (state == 1) s.push({cur->right, 0});
        else if (state == 2) cout << cur->data << " " ;
    }
}

int main() {
/*
   	 1
       /    \
      2      3
    /   \   /  \
   4     5 6    7
*/
    struct Node* root = new Node(1);
  	root->left = new Node(2);
  	root->left->left = new Node(4);
  	root->left->right = new Node(5);
  	root->right = new Node(3);
  	root->right->left = new Node(6);
  	root->right->right = new Node(7);
    iterativeTraversal(root);
    return 0;
}

Report Error/ Suggestion

Related Posts:









CopyRight © 2020

CopyRight © 2020