{"id":27135,"date":"2018-01-03T21:38:52","date_gmt":"2018-01-03T16:08:52","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27135"},"modified":"2018-01-03T21:38:52","modified_gmt":"2018-01-03T16:08:52","slug":"level-order-tree-traversal","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/level-order-tree-traversal\/","title":{"rendered":"C program -Level Order Tree Traversal"},"content":{"rendered":"

Level order traversal of a tree is breadth first traversal for the tree.<\/p>\n

Level order traversal of the above tree is 1 2 3 4 5<\/p>\n

\n

Recommended: Please solve it on “PRACTICE<\/u><\/i><\/b>” first,<\/h2>\n

before moving on to the solution.<\/h2>\n<\/div>\n

METHOD 1 (Use function to print a given level)<\/strong><\/p>\n

Algorithm:<\/strong>
\nThere are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.<\/p>\n

\/*Function to print level order traversal of tree*\/\r\nprintLevelorder(tree)<\/strong>\r\nfor d = 1 to height(tree)\r\n   printGivenLevel(tree, d);\r\n\r\n\/*Function to print all nodes at a given level*\/\r\nprintGivenLevel(tree, level)<\/strong>\r\nif tree is NULL then return;\r\nif level is 1, then\r\n    print(tree->data);\r\nelse if level greater than 1, then\r\n    printGivenLevel(tree->left, level-1);\r\n    printGivenLevel(tree->right, level-1);<\/pre>\n[ad type=”banner”]\n
 
 <\/div> 
\/\/ Recursive C program for level order traversal of Binary Tree#include <stdio.h>#include <stdlib.h> \/* A binary tree node has data, pointer to left child   and a pointer to right child *\/struct node{    int data;    struct node* left, *right;}; \/* Function protoypes *\/void printGivenLevel(struct node* root, int level);int height(struct node* node);struct node* newNode(int data); \/* Function to print level order traversal a tree*\/void printLevelOrder(struct node* root){    int h = height(root);    int i;    for (i=1; i<=h; i++)        printGivenLevel(root, i);} \/* Print nodes at a given level *\/void printGivenLevel(struct node* root, int level){    if (root == NULL)        return;    if (level == 1)        printf("%d ", root->data);    else if (level > 1)    {        printGivenLevel(root->left, level-1);        printGivenLevel(root->right, level-1);    }} \/* Compute the "height" of a tree -- the number of    nodes along the longest path from the root node    down to the farthest leaf node.*\/int height(struct node* node){    if (node==NULL)        return 0;    else    {        \/* compute the height of each subtree *\/        int lheight = height(node->left);        int rheight = height(node->right);         \/* use the larger one *\/        if (lheight > rheight)            return(lheight+1);        else return(rheight+1);    }} \/* Helper function that allocates a new node with the   given data and NULL left and right pointers. *\/struct node* newNode(int data){    struct node* node = (struct node*)                        malloc(sizeof(struct node));    node->data = data;    node->left = NULL;    node->right = NULL;     return(node);} \/* Driver program to test above functions*\/int main(){    struct node *root = newNode(1);    root->left        = newNode(2);    root->right       = newNode(3);    root->left->left  = newNode(4);    root->left->right = newNode(5);     printf("Level Order traversal of binary tree is \\n");    printLevelOrder(root);     return 0;}<\/code><\/pre> <\/div>\n","protected":false},"excerpt":{"rendered":"
Level Order Tree Traversal – Level Order Tree Travers – level order tree travesal – here are basically two functions in this method. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80140,83838],"tags":[80908,80907,80905,80909,80903,80906,80910,80904],"class_list":["post-27135","post","type-post","status-publish","format-standard","hentry","category-binay-tree","category-level-order-tree","tag-level-order-traversal-example","tag-level-order-traversal-in-spiral-form","tag-level-order-traversal-java","tag-level-order-traversal-leetcode","tag-level-order-traversal-of-a-binary-tree-in-c-code","tag-level-order-traversal-of-binary-tree-using-queue-in-c","tag-print-tree-level-by-level-java","tag-reverse-level-order-traversal"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27135","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27135"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27135\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27135"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27135"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27135"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}