Binary Tree Level Order Traversal Algorithm in Go

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]
Example 3:

Input: root = []
Output: []

Implement BFS Algorithm in Go

Traversing the Binary Tree in Level-by-Level Order is typically solved by implementing a Breadth First Search Algorithm. In Go Programming, we have the following implementation – Time complexity O(N) and space complexity is also O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var q = [](*TreeNode){root}
    var ans = [][]int{}
    for len(q) > 0 {
        var curLevel = []int{}
        var sz = len(q)
        for i:=0; i < sz; i++ {
            var cur = q[i]
            curLevel = append(curLevel, cur.Val)
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        q = q[sz:]
        ans = append(ans, curLevel)
    }
    return ans
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var q = [](*TreeNode){root}
    var ans = [][]int{}
    for len(q) > 0 {
        var curLevel = []int{}
        var sz = len(q)
        for i:=0; i < sz; i++ {
            var cur = q[i]
            curLevel = append(curLevel, cur.Val)
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        q = q[sz:]
        ans = append(ans, curLevel)
    }
    return ans
}

The Go doesn’t have while loop but we can totally use the for for it.

The Go doesn’t have queue – but we can use list/array to achieve the same thing: q[0] for begining of the queue, q=q[1:] for deque. And append() function to enqueue.

See also: Binary Tree Level Order Traversal in C/C++

–EOF (The Ultimate Computing & Technology Blog) —