Perform Level Order Traversal on a Binary Tree Using Go

This program demonstrates how to perform a level order traversal of a binary tree. Level order traversal involves visiting all nodes at each depth level from left to right before moving to the next level.

Program Explanation

The approach uses a queue to keep track of nodes to be processed, ensuring that nodes are processed in the correct order of their depth levels. Each node is visited and its children are added to the queue, thus maintaining the order of traversal.

Code Structure

1. TreeNode struct: Defines the structure of the binary tree nodes.
2. levelOrder function: Implements the level order traversal and returns a slice of slices containing node values at each level.

Code with Documentation

package main

import (
    "fmt"
)

// TreeNode defines a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// levelOrder performs level order traversal of the binary tree.
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    
    var result [][]int
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := make([]int, levelSize)
        
        for i := 0; i < levelSize; i++ {
            current := queue[0]
            queue = queue[1:]
            currentLevel[i] = current.Val
            
            if current.Left != nil {
                queue = append(queue, current.Left)
            }
            if current.Right != nil {
                queue = append(queue, current.Right)
            }
        }
        result = append(result, currentLevel)
    }
    
    return result
}

func main() {
    // Construct a simple binary tree:
    //        1
    //       / \
    //      2   3
    //     / \   \
    //    4   5   6
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, &TreeNode{6, nil, nil}}}

    levels := levelOrder(root)
    fmt.Println("Level order traversal of the binary tree:")
    for _, level := range levels {
        fmt.Println(level)
    }
}

Conclusion

The Go code effectively demonstrates a level order traversal of a binary tree, using a queue-based approach to ensure that all nodes are visited in their level-wise sequence. This traversal method is crucial for many tree operations and is commonly used in algorithms such as breadth-first search (BFS).