Leetcode Binary Tree Array Format in Golang

In the Binary Tree section of leetcode, they provide an Input array with values used to create a binary tree.

It isn't necessary to reproduce the trees to solve the traversal problems as you can manually build a tree by adding Left and Right nodes manually.

Still using the input data helps to suss out bugs when it fails some tests. The difficulty I ran into was trying to implement a recursive solution when the approach was understanding (with some googling help) that a queue was needed.

Below are my comments and code.

// create binary tree given a leetcode compressed array

// a verbose version of a binary tree would have a NULL_VALUE

// for every node at the full height eg.

//

// 0

// null 2

//

// null null 3 null

// Input = [0, null, 2, null, null, 3]

//

// leetcode BT format is a little more efficient as it will

// skip the 2 lower nulls

//

// Input = [0, null, 2, 3]

// To build the binary tree use a queue that will allow us to

// process each level before continue to the next level.

// When a node is created we add it to the queue. The L/R logic

// proceeds and pops the next value from the Input array.

// If the value is a null, we don't add it to the queue which stops

// further processing on that branch

//

// We loop until the queue is empty.

func (b *BinaryTree) CreateUnsorted(arr []int) {

if len(arr) <= 0 {

fmt.Println("No Elements")

return

}

val, arr := ArrayPop(arr)

b.Root = &TreeNode{Val: val}

queue := []*TreeNode{b.Root}

var node *TreeNode

leftVal := 0

rightVal := 0

for len(queue) > 0 {

node, queue = ArrayPop(queue)

if len(arr) <= 0 {

continue

}

leftVal, arr = ArrayPop(arr)

if leftVal != NULL_VALUE {

node.Left = &TreeNode{Val: leftVal}

queue = append(queue, node.Left)

}

if len(arr) <= 0 {

continue

}

rightVal, arr = ArrayPop(arr)

if rightVal != NULL_VALUE {

node.Right = &TreeNode{Val: rightVal}

queue = append(queue, node.Right)

}

}

}