Count Complete Tree Nodes

Problem Summary

• Given a Complete Binary Tree return the number of nodes it has

What is Being Asked?

• Count the number of nodes in the tree in less than $O(n)$ time complexity

Key Observations

• Think recursively in simple base cases

Main Concepts Used

• Trees

Time & Space Complexity

• Time: $O(logn)$ → Reason: Every iteration the tree gets cut down in half
• Space: $O(height)$ → Reason: Recursive call stack

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        # case 1: it is a perfect complete binary tree
        # use numOfNodes = 2^levels - 1
        # case 2: it is not a perfect complete binary tree
        # recursively call left and right subtree and add its result and return

        if not root:
            return 0

        isPCBT, levels = self.isPerfectCompleteBinaryTree(root)
        if isPCBT:
            return levels
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def isPerfectCompleteBinaryTree(self, root: Optional[TreeNode]) -> bool:
        leftLevels = 1
        left = root.left
        while left:
            leftLevels += 1
            left = left.left

        rightLevels = 1
        right = root.right
        while right:
            rightLevels += 1
            right = right.right

        answer = leftLevels == rightLevels
        numberOfNodes = (2**leftLevels) - 1
        return answer, numberOfNodes

Common Mistakes / Things I Got Stuck On

• Forgot to add 1 to the return of recursive calls
• Forgot to apply the formula of $2^{levels}-1$
• Used ^ instead of ** for exponent again