Perfect Binary Tree Specific Level Order Traversal in C++

Hello coders! In this tutorial, we will learn how to write the C++ program for Perfect Binary Tree Specific Level Order Traversal. Basically here, we are going to learn how to find all the nodes at the specific levels in a tree.

For example, we are going to print even level order traverse and odd level order traverse. So let us first see about binary trees.

You can learn more about binary tree here Build Binary Tree in C++ (Competitive Programming)

C++ program of Perfect Binary Tree Specific Level Order Traversal

#include <bits/stdc++.h> 
using namespace std; 
class TreeNode  
{  
    public: 
    int val;  
    TreeNode* left, *right;  
    TreeNode(int val){
        this->val = val;  
        this->left = NULL;  
        this->right = NULL;
    }
};   
void printLevel(TreeNode* root, int level)  
{  
    if (root == NULL)  
        return;  
    if (level == 1)  
        cout << root->val << " ";  
    else if (level > 1)  
    {  
        printLevel(root->left, level-1);  
        printLevel(root->right, level-1);  
    }  
}  
int height(TreeNode* root)  
{  
    if (root == NULL)  
        return 0;  
    return (1+max(height(root->left),height(root->right)));
}  
void specificEvenOrder(TreeNode* root)  
{  
    int h = height(root);
    for (int i = 1; i <= h; i++)  
        if(i%2==0)
        printLevel(root, i);  
}
void specificOddOrder(TreeNode* root)  
{  
    int h = height(root);
    for (int i = 1; i <= h; i++)  
        if(i%2==1)
        printLevel(root, i);  
}    
int main()  
{  
    TreeNode *root = new TreeNode(1); 
    root->left        = new TreeNode(2); 
    root->right       = new TreeNode(3); 
    root->left->left  = new TreeNode(4); 
    root->left->right = new TreeNode(5); 
    root->right->left  = new TreeNode(6); 
    root->right->right = new TreeNode(7); 
    root->left->left->left  = new TreeNode(8); 
    root->left->left->right  = new TreeNode(9); 
    root->left->right->left  = new TreeNode(10); 
    root->left->right->right  = new TreeNode(11); 
    root->right->left->left  = new TreeNode(12); 
    root->right->left->right  = new TreeNode(13); 
    root->right->right->left  = new TreeNode(14); 
    root->right->right->right  = new TreeNode(15); 
    root->left->left->left->left  = new TreeNode(16); 
    root->left->left->left->right  = new TreeNode(17); 
    root->left->left->right->left  = new TreeNode(18); 
    root->left->left->right->right  = new TreeNode(19); 
    cout << "Even Level Order traversal\n"; 
    specificEvenOrder(root); cout<<"\n";
    cout << "Odd Level Order traversal\n"; 
    specificOddOrder(root);
    return 0;  
}

Output:

Even Level Order traversal
2 3 8 9 10 11 12 13 14 15
Odd Level Order traversal
1 4 5 6 7 16 17 18 19

Here in this code we first created class TreeNode made a tree in int main() function and also made various functions such as height(), printLevel(), etc.

So hereafter we’re calling functions specificOddOrder() and specificEvenOrder()  we are first finding the height of a left or right subtree and then giving parameters to the printlevel() function which will print the required specific level order traversal on the screen.

Leave a Reply

Your email address will not be published.