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