이진트리(binary tree)의 높이(height)와 직경(diameter)

이진트리의 높이는 root node로부터 가장 먼 leaf node까지의 path상에 있는 node의 개수이고, 직경은 가장 먼 두 개의 노드 사이의 path상에 있는 node의 개수로 정의된다.




먼저 이진트리의 높이를 구하는 방법을 살펴보면, 하나의 노드를 기준으로 높이는 왼쪽 sub-tree의 높이와 오른쪽 sub-tree의 높이 중 보다 큰 것에 나 자신을 하나 더 count하면 구할 수 있다. 왼쪽과 오른쪽 sub-tree의 높이는 동일한 방법을 반복해서 적용하여 구할 수 있고, recursion임을 알 수 있다.
예제 tree에서 높이는 노드1 (root node)부터 노드13, 노드14, 또는 노드15까지의 path로 결정될 것이다.

func GetHeight(node *Node) int {

  if node == nil {

    return 0

  }

  return Max(GetHeight(node.Left), GetHeight(node.Right)) + 1

}

func Max(a, b int) int {

  if a > b {

    return a

  }

  return b

}

Max함수를 작성한 것은 Go가 integer max 함수를 제공하지 않기 때문이다 (math.Max는 float64만 지원)

이진트리의 직경은 높이와 비슷한 방식으로 구할 수 있는데, 특정 노드에서의 직경은 왼쪽 sub-tree에서의 직경, 해당노드를 포함하는 직경, 그리고 오른쪽 sub-tree에서의 직경 중 가장 큰 값으로 결정된다. 역시, 왼쪽/오른쪽 sub-tree에서의 직경은 동일한 방법을 반복 적용하여 구한다.

예제 tree에서의 직경은 노드13(혹은 노드14)에서 노드15까지의 path로 결정된다 (root node입장에서는 나를 지나지 않는 직경인 경우다).

func GetDiameter(node *Node) (int, int) {

  if node == nil {

    return 0, 0

  }

  leftD, leftH := GetDiameter(node.Left)

  rightD, rightH := GetDiameter(node.Right)

  return Max(Max(leftD, rightD), leftH + rightH + 1), Max(leftH, rightH) + 1

}