Tree Traversal Level Order BFS in DSA Go - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: Imagine you have a family tree and you want to visit each generation one by one, starting from the oldest ancestor down to the youngest children.

🎯 Goal: You will build a program that visits nodes of a tree level by level using Breadth-First Search (BFS) and prints the values in order.

📋 What You'll Learn

Create a simple binary tree with exact node values

Use a queue to help with level order traversal

Implement BFS to visit nodes level by level

Print the node values in the order they are visited

💡 Why This Matters

🌍 Real World

Level order traversal is useful in scenarios like printing organizational charts, family trees, or spreading information layer by layer in networks.

💼 Career

Understanding BFS and tree traversal is important for software engineers working with hierarchical data, search algorithms, and many coding interviews.

1

Create the binary tree nodes

Create a binary tree with a root node called root of type *Node. The root node should have the value 1. It should have a left child with value 2 and a right child with value 3. The left child of the root should have two children: left child with value 4 and right child with value 5. Use the Node struct defined below.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func main() {
    // Create the tree nodes as described
    // Your code here
}

Hint

Use the &Node{Val: value} syntax to create nodes and assign them to Left and Right fields.

2

Create a queue to help with BFS

Create a slice of *Node called queue and initialize it with the root node inside it. This queue will help us visit nodes level by level.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    root.Left.Left = &Node{Val: 4}
    root.Left.Right = &Node{Val: 5}

    // Create a queue slice with root node
    // Your code here
}

Hint

Initialize queue as a slice containing only the root node.

3

Implement BFS to traverse the tree level by level

Use a for loop that runs while len(queue) > 0. Inside the loop, remove the first node from queue and store it in current. Then, if current.Left is not nil, append it to queue. Similarly, if current.Right is not nil, append it to queue. Print the value of current.Val inside the loop.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    root.Left.Left = &Node{Val: 4}
    root.Left.Right = &Node{Val: 5}

    queue := []*Node{root}

    // Implement BFS loop here
    // Your code here
}

Hint

Use a loop to remove the first node from queue, print its value, then add its children to the end of queue.

4

Print the final output of BFS traversal

Run the program to print the values of the nodes in level order separated by spaces. The expected output is: 1 2 3 4 5

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    root.Left.Left = &Node{Val: 4}
    root.Left.Right = &Node{Val: 5}

    queue := []*Node{root}

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        fmt.Print(current.Val, " ")

        if current.Left != nil {
            queue = append(queue, current.Left)
        }
        if current.Right != nil {
            queue = append(queue, current.Right)
        }
    }

    // Output is printed inside the loop
    // Your code here
}

Hint

Run the program to see the node values printed in level order separated by spaces.