[코딩 인터뷰][LeetCode] – Count Complete Tree Nodes

※ 이 포스트는 LeetCode 코딩 인터뷰 문제인 Count Complete Tree Nodes의 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, LeetCode에서의 Submission 통과만을 보장합니다.

문제 정보

문제 출처 : https://leetcode.com/problems/count-complete-tree-nodes/submissions/
카테고리 : Binary Search
난이도 : 쉬움 ~ 중간

---

문제 설명

Complete Binary Tree (마지막 level을 제외한 모든 부모 level이 완전히 채워진 Tree)가 주어졌을 때, 이 Tree의 노드 수를 출력하여라.
Tree는 노드를 추가할 때 현재 level에서 삽입 가능한 곳 중 가장 왼쪽에 우선적으로 삽입하는 방식으로 만들어졌다.

---

문제 풀이

SIMPLE – O(N)의 방법
이 문제를 가장 단순하게 푸는 방법은 재귀 호출을 사용하는 방식이다. 각 노드는 자신의 왼쪽, 오른쪽 자식의 정보를 left, right에 저장한다.
Tree의 Root에서 시작해서 자신의 left와 right을 root로 한 subTree의 노드 수의 합에 자기자신을 계산한 +1을 해주면 답이 나온다.
이 아이디어는 재귀적으로 구현할 수 있으며 O(N)의 시간복잡도를 가진다.

위 풀이는 Complete Binary Tree와 노드 삽입 조건 중 어떤 것도 사용하지 않았다.
이 두 조건을 가지고 이분 검색을 수행하면 O((log N)^2)의 수행시간으로 문제를 해결할 수 있다

Binaary Search – O((log N)^2)의 방법
문제 해결 절차는 다음과 같다.

1. Root를 Level 0이라 간주하고, Tree의 최대 Level을 찾는다.
노드는 가능한 왼쪽부터 삽입하기 때문에, Root로부터 왼쪽으로만 탐색할 때, 마지막으로 도달하는 노드는 항상 최대 Level에 속한다.
최대 Level을 L이라고 하면, L – 1까지 Level은 완전하므로 그 노드의 수는 2^L – 1개가 된다.

2. Level L의 노드 수를 찾는다. 가장 오른쪽 노드를 찾을 수 있다면, Level L의 전체 노드 수를 구할 수 있다.
Level L에는 2^L개의 노드가 있고, 가장 왼쪽을 인덱스 0으로 오른쪽을 2^L – 1라고 할 때 인덱스를 L개의 비트로 표현할 수 있다.
알고리즘은 그 비트를 하나씩 찾아나간다. 가장 앞자리의 비트가 1이라는 말은 Root의 오른쪽 Child의 SubTree에 노드가 존재한다는 말이다. 맨 처음에 모든 비트가 0으로 세팅된 상황에서, 가장 앞자리의 비트를 1로 세팅하고 탐색을 시작해보자. 첫 번째를 제외하고는 모두 왼쪽 Child를 선택하게 될테니 도착지점의 인덱스는 2^(L – 1)이 될 것이다. 여기에 노드가 존재하지 않는다면 가장 오른쪽 노드는 이 지점보다 왼쪽에 있다. 따라서 이 비트는 1이 아닌 0이 되어야한다.
이런 방식으로 비트를 1로 설정해 탐색을 해서 마지막에 노드를 발견하면 그대로 두고 아니면 0으로 바꾸는 방식으로 문제를 풀 수 있다.

---

코드

Simple – O(N)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # For empty tree case.
        if root == None:
            return 0
        
        # Recursively return sum of children.
        left, right = 0, 0
        if root.left != None:
            left = self.countNodes(root.left)
        if root.right != None:
            right = self.countNodes(root.right)
        return left + right + 1

Binary Search – O((log N)^2)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # For empty tree case.
        if root == None:
            return 0
        
        # Init Sum and Level
        Sum, L = 0, 0
        # Find Max Level
        cur = root
        while cur.left != None:
            L += 1
            cur = cur.left
        Sum = 2 ** L - 1
        
        # Binary Search and Find right most node in level L.
        Command = [0] * L
        for i in range(L):
            # Set i-th value to 1
            Command[i] = 1
            cur = root
            for cmd in Command:
                cur = cmd == 0 and cur.left or cur.right
            if cur == None:
                Command[i] = 0
        
        # Calc the number of nodes in level L.
        Command.reverse()
        for i in range(L):
            Sum += (2 ** i) * Command[i]
        
        return Sum + 1