Tree: Level Order Traversal


Problem Statement :


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.



Solution :


                            Solution in C :

In C ++ :




/*
struct node
{
    int data;
    node* left;
    node* right;
}*/
int height(node * root)
{
  if(!root)
      return 0;
    int lleft=height(root->left);
    int rright=height(root->right);
    if(lleft > rright)
        return(lleft+1);
    else
        return (rright+1);
}
  void level(node *root,int h){
      if(!root)
          return ;
      if(h==1)
          cout<<root->data<<" ";
      level(root->left,h-1);
      level(root->right,h-1);
  }
void LevelOrder(node * root)
{
  int n=height(root);
    for(int i=1;i<=n;i++){
        level(root,i);
        
    }
  
}




In Java :



   /* 
    
    class Node 
       int data;
       Node left;
       Node right;
   */
   void LevelOrder(Node root)
    {
       Node last = root;
       Queue<Node> q1 = new LinkedList<Node>();
       Queue<Node> q2 = new LinkedList<Node>();
       q1.add(root);
       Node cur = null;
       while (!q1.isEmpty() || !q2.isEmpty()) {
            while (!q1.isEmpty()) {
                cur = q1.poll();
                if (cur.left != null) {
                     q2.add(cur.left);
                }
                if (cur.right != null) {
                     q2.add(cur.right);
                }
                System.out.print(cur.data + " ");
            }
            while (!q2.isEmpty()) {
                cur = q2.poll();    
                if (cur.left != null) {
                    q1.add(cur.left);
                }
                if (cur.right != null) {
                    q1.add(cur.right);
                }
                System.out.print(cur.data + " ");
            }
       }
    }





In python3 :


"""
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)
"""
def levelOrder(root):
    myQ = [root]
    
    while(len(myQ) > 0):
        iter = myQ.pop(0)
        print(iter.info,end = " ")
        if (iter.left != None):
            myQ.append(iter.left)
        if (iter.right != None):
            myQ.append(iter.right)




In C :



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

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

*/int height(struct node* root)
{
    if(!root)
        return 0;
    else
    {
        int rl=height(root->left);
        int rr=height(root->right);
        if(rl>rr)
            return rl+1;
        else
            return rr+1;
    }
}void printlevelorder(struct node* root,int level)
{
    if(!root)
        return;
    else if(level==1)
        printf("%d ",root->data);
    else if(level>1)
    {
        printlevelorder(root->left,level-1);
        printlevelorder(root->right,level-1);
}
}
void levelOrder( struct node *root) {
    int h=height(root);
    int i;
    for(i=0;i<=h;i++)
    {
    printlevelorder(root,i);
    }

}
                        




View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

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 F

View Solution →