Tuesday, October 1, 2024

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)
}
}
}