problem: https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/

bstlevelordertraversal.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Queue struct {
    nodes []*TreeNode
}

func (q *Queue) pop() *TreeNode {
    node := q.nodes[len(q.nodes)-1]
    if len(q.nodes) > 0 {
        q.nodes = q.nodes[:len(q.nodes)-1]
    }
    return node
}

func (q *Queue) add(node *TreeNode) {
    q.nodes = append([]*TreeNode{node}, q.nodes...)
}

func (q *Queue) size() int {
    return len(q.nodes)
}

func NewQueue(root *TreeNode) *Queue {
    return &Queue {[]*TreeNode{root}}
}

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    
    q := NewQueue(root)
    var result [][]int    

    for len(q.nodes) != 0 {
        size := q.size()
        var currLvl []int
        
        for i := 0; i < size; i++ {
            curr := q.pop()
            currLvl = append(currLvl, curr.Val)
            
            if curr.Left != nil {
                q.add(curr.Left)
            }
            if curr.Right != nil {
                q.add(curr.Right)
            }
        }
        result = append(result, currLvl)
    }
    
    return result
}

For the first half of the file, it's mostly helper functions to make a queue like data structure. With pop taking nodes off of the end of a slice and add prepending nodes to a slice. Just like a queue would.

The algorithm is as follows:

- if the root value from input is nil, return nil
- if not, then initialize a new queue with the root node
- create an empty result [][]int to populate as we iterate through the BST
- while the queue still has nodes, do the following
    - set size to be the size of the queue
    - create a new temporary []int called current level to store the neighboring nodes we come across
        - for each neighboring node on the current level, we want to do a few things
            - pop the current node and add its current value to the current level []int
            - then, check to see if current node has a left child, add it to the queue
            - then, check to see if current node has a right child, add it to the queue
        - once we exit the inner for loop, we can add the current level []int to the result
- once we exit the outer while loop, we return result