# 222. Count Complete Tree Nodes

Question link is here.

# Question

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

# Solution

# Solution 1

The first solution is obvious traverse through the tree can count the node, And this solution just run in $O(n)$.

class Solution:
        
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        queue = [root]
        cnt = 0
        while queue:
            node = queue.pop(0)
            cnt += 1
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        return cnt

# Solution 2

We are insured that the input is a complete binary tree, and we can take some advantage of that.

We know the depth of a complete binary tree is the depth of it's left most leaf node, so we can calculate the depth of the root node's left sub-tree $d_{left}$and right sub-tree $d_{right}$. If $d_{left} == d_{right}$ the left sub-tree is a full binary tree, and we can calculate its node number: $2^{d_{left}} - 1$, plus the root node, makes it total $2^{d_{left}}$ nodes. And we can now apply the same method to root's right subtree. And if $d_{left} \neq d_{right}$, then the right sub-tree is a full binary tree, and we can use the same method before.

class Solution {
    public int computeDepth(TreeNode node) {
        if(node == null)
            return 0;
        int res = 0;
        while(node != null) {
            res += 1;
            node = node.left;
        }
        return res;
    }
    
    public int countNodes(TreeNode root) {
        int res = 0;
        if(root == null)
            return res;
        int left = 0;
        while(root != null) {
            if(left == 0)
                left = computeDepth(root.left);
            else
                left = left - 1;
            int right = computeDepth(root.right);
            if(left == right){
                res += Math.pow(2, left);
                root = root.right;
            } else {
                res += Math.pow(2, right);
                root = root.left;
            }
        }
        return res;
    }
}

class Solution:
    def compute_depth(self, node: TreeNode) -> int:
        if node is None:
            return 0
        res = 0
        while node is not None:
            res += 1
            node = node.left
        return res
        
    def countNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        res = 0
        left = 0
        while root is not None:
            if left == 0:
                left = self.compute_depth(root.left)
            else:
                left = left - 1
            right = self.compute_depth(root.right)
            if left == right:
                res += 2** left
                root = root.right
            else:
                res += 2 ** right
                root = root.left
        return res

Time Complexity: $O(d^2) = O((log_2^n)^2)$