We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Complete Tree Nodes

Number: 222

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Meta, Amazon, Apple, Bloomberg, TikTok

Problem Description

Given the root of a complete binary tree, count the total number of nodes. A complete binary tree has every level fully filled except possibly the last level, and all nodes in the last level are as far left as possible. The challenge is to design an algorithm that runs in less than O(n) time complexity.

Key Insights

  • A complete binary tree has properties that allow us to calculate parts of the tree quickly.
  • Compute the depth of the left-most path and the right-most path:
    • If they are equal, the tree is perfect and the number of nodes is 2^depth - 1.
    • If not equal, recursively count nodes in the left and right subtrees.
  • This approach reduces the time complexity to O((log n)^2) versus a straightforward O(n) traversal.

Space and Time Complexity

Time Complexity: O((log n)^2) – each level requires O(log n) comparisons and the height is O(log n).
Space Complexity: O(log n) – due to recursive stack if using recursion.

Solution

We use a recursive strategy:

  1. Define two helper functions to determine the depth along the left-most and right-most branches.
  2. Compare these depths:
    • If equal, the tree is a perfect binary tree and the number of nodes can be calculated using the formula 2^depth - 1.
    • If not equal, the tree is not fully perfect, so we recursively count the nodes in the left and right subtrees and add one for the root.
  3. This algorithm uses the properties of a complete binary tree to avoid traversing every node, achieving a faster solution.

Data Structures and Algorithms:

  • Binary tree traversal (depth-first search style).
  • Recursion.
  • Bit manipulation (via power of two computation when the tree is perfect).

Key trick: Quickly determine subtree perfection by comparing leftmost and rightmost depths.

Code Solutions

# Python Solution

# 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:
    # Helper function to compute the left depth of the tree.
    def leftDepth(node: TreeNode) -> int:
        depth = 0
        while node:
            depth += 1
            node = node.left
        return depth

    # Helper function to compute the right depth of the tree.
    def rightDepth(node: TreeNode) -> int:
        depth = 0
        while node:
            depth += 1
            node = node.right
        return depth

    if not root:
        return 0

    left_depth = leftDepth(root)
    right_depth = rightDepth(root)

    # If left and right depth are the same, tree is perfect.
    if left_depth == right_depth:
        return (1 << left_depth) - 1  # equivalent to 2^left_depth - 1
    else:
        # Recursively count nodes in left and right subtree plus one for root.
        return 1 + countNodes(root.left) + countNodes(root.right)
    
# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(3))
# print(countNodes(root))
← Back to All Questions