Write a O(n) method PrintLevelOrder that prints the nodes of a binary tree in le

Question

Write a O(n) method PrintLevelOrder that prints the nodes of a binary tree in level-order. That is, the method should print the root, then the nodes at depth 1, followed by the nodes at depth 2, and so on. Your algorithm should begin by putting the tree root on an initially empty queue. Then dequeue a node, print its value, and enqueue its left and right children (if they exist). Repeat until the queue is empty.

Explanation / Answer

Here is what you need. Please rate if you like it :) #include #include /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* 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; idata); 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 "); printLevelOrder(root); getchar(); return 0; } Cheers!

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.