Binary Tree: Level order traversal of a Binary Tree

Problem Statement:

Given a binary tree, perform level order traversal.

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Output:

10
8 12
2 9 11 14

Solution 1: using recursion

Get the height of the tree.
Then for each level, print the node values.

Time Complexity: O(n*n)
Space Complexity: O(n)

Solution 2: using queue

We will use queue to solve the problem.

Start buy adding the root into the queue.

Then remove the node from the queue and add its left and right children into the queue.

During that process, get the size of the queue and count the number of nodes, run a loop to print the nodes.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void get_level_nodes(Node *root, int level, vector<int> &levelNodes) 
{
    if (root == NULL)
        return;
    if (level == 1) 
    {
        levelNodes.push_back(root->data);
    }
    else if (level > 1) 
    {
        get_level_nodes(root->left, level - 1, levelNodes);
        get_level_nodes(root->right, level - 1, levelNodes);
    }
}

int get_height(Node *node) 
{
    if (node == NULL)
        return 0;

    int lheight = get_height(node->left);
    int rheight = get_height(node->right);

    if (lheight > rheight) 
    {
        return lheight + 1;
    }
    else 
    {
        return rheight + 1;
    }
}

vector<vector<int>> solution_1(Node *root) 
{
    vector<vector<int>> result;
    int h = get_height(root);

    for (int i = 1; i <= h; i++) 
    {
        vector<int> levelNodes;
        get_level_nodes(root, i, levelNodes);
        result.push_back(levelNodes);
    }

    return result;
}

vector<vector<int>> solution_2(Node* root) 
{
    vector<vector<int>> result;
    if (root == nullptr)
        return result;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) 
    {

        int nodeCount = q.size();
        vector<int> currentLevel;

        for(int i = 0; i < nodeCount; i++) 
        {
            Node* node = q.front();
            q.pop();
            currentLevel.push_back(node->data);

            if (node->left != nullptr)
                q.push(node->left);

            if (node->right != nullptr)
                q.push(node->right);
        }
        result.push_back(currentLevel);
    }

    return result;
}

void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}



int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    vector<vector<int>> traversal = solution_1(root);

    cout << "Solution 1 : "<<endl;

    for (const auto& level : traversal) 
    {
        for (int val : level) 
        {
            cout << val << " ";
        }
        cout << endl;
    }

    traversal = solution_2(root);

    cout << "Solution 2 : "<<endl;

    for (const auto& level : traversal) 
    {
        for (int val : level) 
        {
            cout << val << " ";
        }
        cout << endl;
    }


    return 0;
}

Output

Solution 1 : 
10 
8 12 
2 9 11 14 
Solution 2 : 
10 
8 12 
2 9 11 14