algoadvance

LeetCode 222: Count Complete Tree Nodes

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

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

Example 1:

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

Example 2:

Input: root = []
Output: 0

Clarifying Questions

1. Q: Can the input tree be null? A: Yes, if the input tree is null, the output should be 0.

2. Q: What is the maximum height of the tree? A: The height h of the tree is such that the total number of nodes n ≤ 2^h - 1.

Strategy

A complete binary tree has special properties which allow us to count nodes more efficiently than a simple traversal.

1. Depth Calculation:
   • Calculate the depth of the leftmost path.
2. Perfect Tree Check:
   • If the subtree rooted at left child of root and the subtree rooted at right child of root have the same depth, the left subtree is a perfect binary tree.
   • Otherwise, the right subtree is a perfect binary tree.
3. Recursive Counting:
   • When the left and right depths are the same, count the nodes in the left subtree plus the right subtree.
   • Otherwise, count the nodes in the right subtree plus the left subtree.

The following approach uses binary search and properties of a complete binary tree to count nodes efficiently.

Code Implementation

# 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
        
def countNodes(root: TreeNode) -> int:
    if not root:
        return 0
    
    # Function to compute the depth of the leftmost path
    def compute_depth(node):
        depth = 0
        while node:
            node = node.left
            depth += 1
        return depth

    left_depth = compute_depth(root.left)
    right_depth = compute_depth(root.right)

    if left_depth == right_depth:
        return (1 << left_depth) + countNodes(root.right)
    else:
        return (1 << right_depth) + countNodes(root.left)

Time Complexity

• The time complexity for computing the depth of the tree is O(h) where h is the height of the tree.
• The binary tree is a complete binary tree that reduces the problem size by half at each step.
• Therefore, the overall time complexity is O(h^2), where h is the height of the tree. Since h is log(n) in the worst case, the time complexity can also be considered O((log n)^2), where n is the number of nodes in the tree.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?