오름차순으로 정렬된 배열로 부터 가장 높이가 낮은 이진 검색 트리 생성 (binary search tree)

오른차순으로 정렬된 배열이 주어졌을 때, 이를 가장 높이가 낮은 이진 검색 트리로 변환하는 코드를 작성한다.
정렬된 배열의 임의의 원소를 선택하더라도, 그 왼쪽 sub-array와 오른쪽 sub-array이 모두 정렬된 상태이므로, 선택한 원소를 key로 갖는 노드를 생성하고 노드의 왼쪽 자식과 노드의 오른쪽 자식은 재귀 호출을 사용하여 이진 검색 트리를 생성할 수 있다. 이 작업의 반복을 최소화 하기 위해서는 왼쪽과 오른쪽의 sub-array의 크기가 동일하거나 1만큼의 차이가 나도록 원소를 선택하면 된다.

type NodeVal int

type Node struct {

    Val   NodeVal

    Left  *Node

    Right *Node
}

func CreateShortestBST(sortedData []NodeVal) *Node {

    return CreateShortestBSTUtil(sortedData, 0, len(sortedData) - 1)

}

func CreateShortestBSTUtil(sortedData []NodeVal, from, to int) *Node {

    if to < from {

        return nil

    }

    mid := from + (to - from) / 2

    node := &Node{

        Val: sortedData[mid],

        Left: CreateShortestBSTUtil(sortedData, from, mid - 1),

        Right: CreateShortestBSTUtil(sortedData, mid + 1, to),

    }

    return node
}