이진 검색 트리 (binary search tree)의 Inorder Successor

이진 검색 트리에서 중위 순회의 순서상 다음 노드를 찾아 보자.
찾으려는 노드는 주어진 노드 key값보다 큰 것중 가장 작은 key 값을 갖는다. 별도의 공간을 사용할 수 있다면, inorder traversal을 수행 하여 정렬된 key 배열을 얻은 후, 주어진 노드의 바로 오른쪽 노드를 찾는다.
아래에서는 별도의 공간을 사용하지 않고 찾는 방법을 구현한다. 이 문제는 주어진 노드가 오른쪽 sub-tree를 갖을 때와 그렇지 않을 때로 구분하여 처리할 수 있다. 오른쪽 sub-tree가 있는 경우에는 오른쪽 sub-tree에 있는 노드 중 가장 작은 값을 선택하면 된다. 오른쪽 sub-tree가 없는 경우에는 root로부터 주어진 노드로 탐색을 하면서 successor 값을 갱신하고, 주어진 노드에 도달했을 때의 successor가 찾는 노드이다. 탐색 시 successor 값은 왼쪽 sub-tree로 이동할 때만 갱신을 한다.

func InorderSuccessor(root, node *Node) *Node {

    if root == nil || node == nil {

        return nil

    }

    if node.Right != nil {

        successor := node.Right

        for successor.Left != nil {

            successor = successor.Left

        }

        return successor

    }

    var successor *Node

    indicator := root

    for indicator != node && indicator != nil {

        switch {

        case node.Val < indicator.Val:

            successor = indicator

            indicator = indicator.Left

        case node.Val > indicator.Val:

            indicator = indicator.Right

        case node.Val == indicator.Val:

            return successor

        }

    }

    return nil
}