Binary Tree Traversal!!!

Breadth-First

• Or called Level-Order

• Visit all nodes at a depth (or level) before visiting the nodes a deep level

• We can use a Queue to print level-order

In our code we can include Queue:

#include <queue>
using std::queue;

Code for Level-Order Traversal

#include<iostream>
using std::cout;
using std::endl;

#include <queue>
using std::queue;


struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

Node* Insert(Node *root,int data) {
	// Return pointer which is a memory address

	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	
	else if(data <= root->data)
	{	
		root->left = Insert(root->left,data);
	}
	else 
	{
		root->right = Insert(root->right,data);
	}
	return root;  // Return Root Address
}

void printLevelOrder(Node *root)
{
    // Base Case
    if (root == NULL)
	{
		return;
	} 
    queue<Node*> q;
 
    q.push(root);
	
    while (q.empty() == false) 
    {
        int NodeCount = q.size();

        while (NodeCount > 0)
        {
            Node *Node = q.front();
            cout << Node->data << " ";
            q.pop();
            if (Node->left != NULL)
                q.push(Node->left);
            if (Node->right != NULL)
                q.push(Node->right);
            NodeCount--;
        }
        cout << endl;
    }
}

int main() {

	Node* root = NULL;

	root = Insert(root,15); 
	root = Insert(root,10); 	
	root = Insert(root,20);
	root = Insert(root,17); 
	root = Insert(root,25); 
	root = Insert(root,19); 
	root = Insert(root,18); 
	root = Insert(root,7); 
	root = Insert(root,14);
	root = Insert(root,5);
	root = Insert(root,9);

   	printLevelOrder(root);
}

Output:

15 
10 20 
7 14 17 25 
5 9 19 
18 

Depth-First

Preorder Traversal

Preorder -

Logic:

1. Check if the current node is empty/NULL
2. Display the data of the Node
3. Traverse the left-subtree using recursion calling the pre-order function
4. Traverse the right-subtree using recursion calling the pre-order function

Code for Preorder

void preorder(Node* root)
{
      if (root == NULL )
    {
        return;
    }
    cout << root->data << " ";

    preorder(root->left);

    preorder(root->right);
}

Inorder Traversal

Inorder -

Logic:

1. Check if the current node is empty/NULL (Don’t print the root node)
2. Traverse the left-subtree using recursion calling the in-order function
3. Display the data part of the Node
4. Traverse the right-subtree using recursion calling the in-order function

Code for Inorder

void inorder(Node* root)
{
    if (root == NULL )
    {
        return;
    }

    inorder(root->left);

    cout << root->data << " ";

    inorder(root->right);
}

Postorder Traversal

Postorder -

Logic:

1. Check if the current node is empty/NULL (Don’t print the root node)
2. Traverse the left-subtree using recursion calling the postorder function
3. Traverse the right-subtree using recursion calling the postorder function
4. Print the data in the node (AKA visit the Node)

Code for Postorder

void postorder(Node* root)
{
    if (root == NULL )
    {
        return;
    }

    postorder(root->left);

    postorder(root->right);

    cout << root->data << " ";
}

Full code using all 3 Pre,In, and Post Orders

#include<iostream>
using std::cout;
using std::endl;

#include <queue>
using std::queue;


struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

Node* Insert(Node *root,int data) {
	// Return pointer which is a memory address

	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	
	else if(data <= root->data)
	{	
		root->left = Insert(root->left,data);
	}
	else 
	{
		root->right = Insert(root->right,data);
	}
	return root;  // Return Root Address
}


void preorder(Node* root)
{
    if (root == NULL )
    {
        return;
    }
    cout << root->data << " ";

    preorder(root->left);
    preorder(root->right);
}

void inorder(Node* root)
{
    if (root == NULL )
    {
        return;
    }
    inorder(root->left);

    cout << root->data << " ";

    inorder(root->right);
}


void postorder(Node* root)
{
    if (root == NULL )
    {
        return;
    }

    postorder(root->left);
    postorder(root->right);

    cout << root->data << " ";
}

int main() {

	Node* root = NULL;

	root = Insert(root,15); 
	root = Insert(root,10); 	
	root = Insert(root,20);
	root = Insert(root,25); 
	root = Insert(root,23); 
	root = Insert(root,7); 
	root = Insert(root,13);
	root = Insert(root,14);
	root = Insert(root,11);

    cout << "Preorder: ";
   	preorder(root);
    cout << endl;

    cout << "Inorder: ";
    inorder(root);
    cout << endl;

    cout << "Postorder: ";
    postorder(root);
    cout << endl;
}

Output:

Preorder: 15 10 7 13 11 14 20 25 23 
Inorder: 7 10 11 13 14 15 20 23 25 
Postorder: 7 11 14 13 10 23 25 20 15