Algorithm


Problem Name: Data Structures - Tree: Level Order Traversal

Problem Link: hhttps://www.hackerrank.com/challenges/tree-level-order-traversal/problem?isFullScreen=true

In this HackerRank in Data Structures - Tree: Level Order Traversal solutions

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, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space.

For example:

 

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4  

For the above tree, the level order traversal is

1- > 2- > 5- > 3- > 6- > 4.

Input Format

You are given a function,

void levelOrder(Node * root) {

}

Constraints

1 <= Nodes in the tree <= 500

Output Format

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

Sample Input

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4  

Sample Output

1 2 5 3 6 4

Explanation

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

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

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

struct node* insert( struct node* root, int data ) {
		
	if(root == NULL) {
	
        struct node* node = (struct node*)malloc(sizeof(struct node));

        node->data = data;

        node->left = NULL;
        node->right = NULL;
        return node;
	  
	} else {
      
		struct node* cur;
		
		if(data  < = root->data) {
            cur = insert(root->left, data);
            root->left = cur;
		} else {
            cur = insert(root->right, data);
            root->right = cur;
		}
	
		return root;
	}
}

/* you only have to complete the function given below.  
node is defined as  

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

*/
void levelOrder( struct node *root) {
    
    struct node      *queue[500];
    int               queue_head, queue_end;
    struct node      *head;
      
    if (!root)
        return;
    
    queue[0] = root;
    queue_head = 0;
    queue_end = 1;
    
    while (queue_head  <  queue_end)
    {
        head = queue[queue_head++];
        fprintf(stdout, "%d ", head->data);
        if (head->left)
            queue[queue_end++] = head->left;
        if (head->right)
            queue[queue_end++] = head->right;
    }
}


int main() {
  
    struct node* root = NULL;
    
    int t;
    int data;

    scanf("%d", &t);

    while(t-- > 0) {
        scanf("%d", &data);
        root = insert(root, data);
    }
  
	levelOrder(root);
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>  

using namespace std;

class Node {
    public:
        int data;
        Node *left;
        Node *right;
        Node(int d) {
            data = d;
            left = NULL;
            right = NULL;
        }
};

class Solution {
    public:
      Node* insert(Node* root, int data) {
            if(root == NULL) {
                return new Node(data);
            } else {
                Node* cur;
                if(data  < = root->data) {
                    cur = insert(root->left, data);
                    root->left = cur;
                } else {
                    cur = insert(root->right, data);
                    root->right = cur;
               }

               return root;
           }
        }
/*
class Node {
    public:
        int data;
        Node *left;
        Node *right;
        Node(int d) {
            data = d;
            left = NULL;
            right = NULL;
        }
};
*/

    void levelOrder(Node * root) {
queue < Node*> q;
        q.push(root);
        while (!q.empty())
        {
            Node* root = q.front();
            q.pop();
            cout << root->data << ' ';
            if (root->left) q.push(root->left);
            if (root->right) q.push(root->right);
        }

    }

}; //End of Solution

int main() {
  
    Solution myTree;
    Node* root = NULL;
    
    int t;
    int data;

    std::cin >> t;

    while(t-- > 0) {
        std::cin >> data;
        root = myTree.insert(root, data);
    }
  
  myTree.levelOrder(root);
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.util.*;
import java.io.*;

class Node {
    Node left;
    Node right;
    int data;
    
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

    /* 
    
    class Node 
        int data;
        Node left;
        Node right;
    */
    public static void levelOrder(Node root)
{
    LinkedList < Node> nodes = new LinkedList();
    
    nodes.add(root);
    
    while(!nodes.isEmpty())
    {
        if(nodes.peek().left != null)
            nodes.add(nodes.peek().left);
        
        if(nodes.peek().right != null)
            nodes.add(nodes.peek().right);
        
        System.out.print(nodes.poll().data + " ");
    }
}
    public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt(>;
        Node root = null;
        while(t-- > 0) {
            int data = scan.nextInt();
            root = insert(root, data);
        }
        scan.close();
        levelOrder(root);
    }   
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


class Node:
    def __init__(self, info): 
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 

class BinarySearchTree:
    def __init__(self): 
        self.root = None

    def create(self, val):  
        if self.root == None:
            self.root = Node(val)
        else:
            current = self.root
         
            while True:
                if val < current.info:
                    if current.left:
                        current = current.left
                    else:
                        current.left = Node(val)
                        break
                elif val > current.info:
                    if current.right:
                        current = current.right
                    else:
                        current.right = Node(val)
                        break
                else:
                    break

"""
Node is defined as
self.left (the left child of the node)
self.right (the right child of the node)
self.info (the value of the node)
"""
from collections import deque

def levelOrder(root):
    #Write your code here
    if not root: return 
    
    queue = deque()
    queue.append(root)
    while queue:
        el = queue.popleft()
        print(el.info, end = ' ')
        if el.left: 
            queue.append(el.left)
        if el.right: 
            queue.append(el.right)



tree = BinarySearchTree()
t = int(input())

arr = list(map(int, input().split()))

for i in range(t):
    tree.create(arr[i])

levelOrder(tree.root)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Tree : Top View solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Binary Search Tree : Insertion solution in Hackerrank - Hacerrank solution C, C++, java,js, Python