Level order traversal is also called breadth first traversal for the tree.
Non-Recursive solution of the problem is – Non-recursive Level Order Traversal
Approach:
There are basically two functions in this method. One is to print all nodes at a given level (printLevel), and other is to get height of tree and print level wise nodes.
struct node { int data; struct node* left; struct node* right; }; void printGivenLevel(struct node* root, int level); int height(struct node* node); /* 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++) printLevel(root, i); } /* Print nodes at a given level */ void printLevel(struct node* root, int level) { if(root == NULL) return; if(level == 1) printf("%d ", root->data); else if (level > 1) { printLevel(root->left, level-1); printLevel(root->right, level-1); } } /* Compute the "height" of a tree */ int height(struct node* node) { if (node==NULL) return 0; else { int lheight = height(node->left); int rheight = height(node->right); if (lheight > rheight) return(lheight+1); else return(rheight+1); } }
Time Complexity: O(n^2) in worst case. For a skewed tree
why height+1
Considering the root node. Since the root node is part of both the left and the right subtree.