Tree: Level Order Traversal Hackerrank problem solution

Tree: Level Order Traversal Hackerrank

You are given a pointer to the root of a binary tree. You need to print the level order traversal of this tree. In level order traversal, we visit the nodes level by level from left to right.
You only have to complete the function.
For example:

3
/ \
5 2
/ \ /
1 4 6

For the above tree, the level order traversal is 3 -> 5 -> 2 -> 1 -> 4 -> 6.

Input Format

You are given a function,

void level_order(node * root)
{

}

Output Format

Print the values in a single line seperated by a space.


Sample Input

3
/ \
5 2
/ \ /
1 4 6


Sample Output

3 5 2 1 4 6
Explanation

Level 1: 3
/ \
Level 2: 5 2
/ \ /
Level 3: 1 4 6

We need to print the nodes level by level. We process each level from left to right.
Level Order Traversal: 3 -> 5 -> 2 -> 1 -> 4 -> 6

Solution

A level-order traversal of a tree, , is a recursive algorithm that processes the root, followed by the children of the root (from left to right), followed by the grandchildren of the root (from left to right), etc. The basic pseudocode algorithm shown below uses a queue of references to binary trees to keep track of the subtrees at each level:
levelOrder(BinaryTree t){
// current root exists
if(t is not empty)

// add root to a queue maintaining level order
queue.enqueue(t)

// while there are elements in the current level’s queue
while( queue is not empty ){

// dequeue a tree
BinaryTree tree = queue.dequeue();

// perform some action, like printing
process tree’s root;

// Add grandchildren to queue from left to right, queue maintains order
// if the dequeued tree has left child, add it to the level queue
if( tree has non-empty left subtree ){
queue.enqueue( left subtree of t)
}
// if the dequeued tree has right child, add it to the level queue
if( tree has non-empty right subtree ){
queue.enqueue( right subtree of t )
}
}
}
}

/*
struct node
{
    int data;
    node* left;
    node* right;
}*/

#include <queue>

void LevelOrder(node * root)
{
    queue<node*> nodes;
    if (root) nodes.push(root);
    for (; !nodes.empty(); nodes.pop())
    {
        cout<<nodes.front()->data<<' ';
        if (nodes.front()->left) nodes.push(nodes.front()->left);
        if (nodes.front()->right) nodes.push(nodes.front()->right);
    }
}
static Queue<Node> queue = new LinkedList<Node>();

static void levelOrder(Node root){
    if( root != null ){
        queue.add(root);
    }
    while( !queue.isEmpty() ){
        Node tree = queue.remove();
        System.out.print(tree.data + " ");

        if( tree.left != null ){
            queue.add( tree.left );
        }
        if( tree.right != null ){
            queue.add( tree.right );
        }
    }
}
deque<Node*> treeQueue;

void levelOrder(Node* root){
    if( root ){
        treeQueue.push_back(root);
    }
    while( !treeQueue.empty() ){  
        Node* tree = treeQueue.front();
        treeQueue.pop_front();

        cout << tree->data << " ";

        if( tree->left ){
            treeQueue.push_back( tree->left );
        }
        if( tree->right ){
            treeQueue.push_back( tree->right );
        }
    }
}


A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.