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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Complete Tree Nodes

Difficulty: Easy

Problem Description

Given the root of a complete binary tree, return the number of nodes in the tree. Every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Key Insights

  • A complete binary tree has a specific structure that allows us to efficiently count nodes.
  • The height of the tree can be determined by traversing down the leftmost path.
  • The number of nodes in a complete binary tree can be calculated using the height and properties of binary trees.

Space and Time Complexity

Time Complexity: O(log^2 n)
Space Complexity: O(1)

Solution

To count the nodes in a complete binary tree, we can take advantage of its properties. First, we compute the height of the tree. Then, we can perform a binary search on the last level to determine how many nodes exist at that level. This approach allows us to count the nodes in less than O(n) time.

  1. Compute the height of the tree by traversing down the leftmost nodes.
  2. Use binary search on the last level (which is indexed) to find the total number of nodes.

Code Solutions

def countNodes(root):
    if not root:
        return 0

    def getHeight(node):
        height = 0
        while node:
            height += 1
            node = node.left
        return height

    height = getHeight(root) - 1
    if height < 0:
        return 0

    def exists(index, height, node):
        left, right = 0, (1 << height) - 1  # 2^height - 1
        for _ in range(height):
            mid = (left + right) // 2
            if index <= mid:
                node = node.left
                right = mid
            else:
                node = node.right
                left = mid + 1
        return node is not None

    left, right = 0, (1 << height) - 1  # 2^height - 1
    while left <= right:
        mid = (left + right) // 2
        if exists(mid, height, root):
            left = mid + 1
        else:
            right = mid - 1

    return left
← Back to All Questions