package main

import (
    "fmt"
    "strings"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var path []int
var output []string

func BinaryTreePaths(head *TreeNode) []string {
    if nil == head {
        return make([]string, 0)
    }

    path = make([]int, 0, 5)
    output = make([]string, 0, 5)

    walk(head)

    return output
}

func walk(curNode *TreeNode) {
    if 0 != curNode.Val {
        path = append(path, curNode.Val)
    }

    if nil != curNode.Left {
        walk(curNode.Left)
    }

    if nil != curNode.Right {
        walk(curNode.Right)
    }

    if nil == curNode.Left && nil == curNode.Right {
        output = append(output, generateOutput("->"))
    }
    path = deleteLastElement(path)
}

func deleteLastElement(slice []int) []int {
    if len(slice) > 0 {
        return slice[:len(slice)-1]
    }

    return make([]int, 0, 5)
}

func generateOutput(delim string) string {
    return strings.Trim(strings.Join(strings.Split(fmt.Sprint(path), " "), delim), "[]")
}

func CreateNode(val int, left *TreeNode, right *TreeNode) *TreeNode {
    var node TreeNode
    node.Val = val
    node.Left = left
    node.Right = right

    return &node
}

func InitNode(val int) *TreeNode {
    return CreateNode(val, nil, nil)
}

func arrayToTree(data []int) *TreeNode {
    var count = len(data)
    if count == 0 {
        return nil
    }

    var head = InitNode(data[0])
    var curNode = head

    for i := 1; i < count; {
        if i < count && data[i] != 0 {
            curNode.Left = InitNode(data[i])
        } else {
            curNode.Left = nil
        }

        i += 1

        if i < count && data[i] != 0 {
            curNode.Right = InitNode(data[i])
        } else {
            curNode.Right = nil
        }

        i += 1

        if curNode.Left != nil && curNode.Left.Val != 0 {
            curNode = curNode.Left
        } else {
            curNode = curNode.Right
        }
    }

    return head
}

func main() {
    var head = arrayToTree([]int{1, 2, 3, 0, 5})
    var res = BinaryTreePaths(head)

    fmt.Printf("%v, ", res)
}