{"id":652,"date":"2024-10-10T13:41:48","date_gmt":"2024-10-10T08:11:48","guid":{"rendered":"https:\/\/codexplained.in\/?p=652"},"modified":"2025-11-24T15:57:07","modified_gmt":"2025-11-24T10:27:07","slug":"level-order-traversal-of-binary-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=652","title":{"rendered":"Level Order Traversal of Binary Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define the structure for a binary tree node\nstruct Node {\n    int data;\n    struct Node *left, *right;\n};\n\n\/\/ Function to create a new tree node\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->left = newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function to print the level order traversal\nvoid levelOrderTraversal(struct Node* root) {\n    if (root == NULL)\n        return;\n\n    \/\/ Create a queue (using an array for simplicity)\n    struct Node* queue[100];\n    int front = 0, rear = 0;\n\n    \/\/ Enqueue the root node\n    queue[rear++] = root;\n\n    while (front < rear) {\n        \/\/ Dequeue a node from the queue\n        struct Node* current = queue[front++];\n        \n        \/\/ Print the current node's data\n        printf("%d ", current->data);\n\n        \/\/ Enqueue the left child if it exists\n        if (current->left != NULL)\n            queue[rear++] = current->left;\n\n        \/\/ Enqueue the right child if it exists\n        if (current->right != NULL)\n            queue[rear++] = current->right;\n    }\n}\n\n\/\/ Main function to test the above code\nint main() {\n    \/\/ Create the root node and other nodes\n    struct Node* root = createNode(1);\n    root->left = createNode(2);\n    root->right = createNode(3);\n    root->left->left = createNode(4);\n    root->left->right = createNode(5);\n    root->right->left = createNode(6);\n    root->right->right = createNode(7);\n\n    printf("Level Order Traversal of the Binary Tree:\\n");\n    levelOrderTraversal(root);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation:<\/h3>\n\n\n\n
    \n
  1. Structure Definition:<\/strong>\n
      \n
    • We define a struct<\/code> called Node<\/code> to represent each node in the tree. It has:\n
        \n
      • int data<\/code>: To store the node’s value.<\/li>\n\n\n\n
      • struct Node* left<\/code>: Pointer to the left child.<\/li>\n\n\n\n
      • struct Node* right<\/code>: Pointer to the right child.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Create Node Function:<\/strong>\n
          \n
        • The createNode<\/code> function allocates memory for a new node, assigns it the provided data, and sets its left and right pointers to NULL<\/code> (indicating no children initially).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Level Order Traversal Function:<\/strong>\n
            \n
          • We handle an empty tree scenario using if (root == NULL) return;<\/code>.<\/li>\n\n\n\n
          • We use an array as a simple queue. The front<\/code> and rear<\/code> indices help track the front and back of the queue.<\/li>\n\n\n\n
          • Initially, the root node is added to the queue.<\/li>\n\n\n\n
          • A while<\/code> loop runs as long as there are nodes in the queue.\n
              \n
            • We dequeue the front node, print its data, and enqueue its left and right children if they exist.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Main Function:<\/strong>\n
                \n
              • Here, we create a sample binary tree and call the levelOrderTraversal<\/code> function.<\/li>\n\n\n\n
              • The tree structure looks like this:<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                     1\n    \/ \\\n   2   3\n  \/ \\ \/ \\\n 4  5 6  7\n<\/code><\/pre>\n\n\n\n
                Output:<\/p>\n\n\n\n
                Level Order Traversal of the Binary Tree:\n1 2 3 4 5 6 7\n<\/code><\/pre>\n\n\n\n
                Explanation of the Output:<\/strong><\/p>\n\n\n\n
                  \n
                • The output reflects the level-by-level order of the binary tree.<\/li>\n\n\n\n
                • Starting with the root (1), we move to the next level (2 and 3), then to the subsequent level (4, 5, 6, 7).<\/li>\n<\/ul>\n\n\n\n
                  Key Points:<\/h3>\n\n\n\n
                    \n
                  • Using a queue is essential to maintain the order of nodes as we process them level by level.<\/li>\n\n\n\n
                  • This approach ensures that each node is visited exactly once, making the time complexity O(n)<\/code>, where n<\/code> is the number of nodes in the tree.<\/li>\n\n\n\n
                  • Memory complexity depends on the maximum number of nodes at any level (breadth of the tree), typically O(width)<\/code> of the tree.<\/li>\n<\/ul>\n\n\n\n
                    <\/p>\n