Count Complete Tree Nodes

Efficiently count nodes in a complete binary tree using height comparisons.

binary-tree complete-tree tree-traversal recursion

A complete binary tree is a binary tree where 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 at the last level h (where h is the height from root, root level is 0).

Write a function `count_nodes(root)` that takes the root of a complete binary tree and returns the total number of nodes. The tree is guaranteed to be complete. The root is represented as a dictionary with keys `'val'`, `'left'`, and `'right'`; `'left'` and `'right'` are either similar dictionaries or `None`. You may assume the tree is already built using this dictionary representation.

Your algorithm should run in less than O(n) time. Optimize by using the property that one of the subtrees is always a perfect binary tree.

The function should return an integer count.

Constraints

- The number of nodes in the tree is in the range [1, 10^5].
- 0 <= Node.val <= 10^4
- The tree is guaranteed to be complete.
- Expected time complexity: O(log^2 n). Avoid visiting every node.

Example

>>> # Complete tree: root = {'val':1, 'left':{'val':2, 'left':{'val':4}, 'right':{'val':5}}, 'right':{'val':3, 'left':{'val':6}, 'right':None}}
>>> count_nodes(root)
6

>>> # Single node tree
>>> count_nodes({'val':1})
1

>>> # More examples:
>>> root = {'val':1, 'left':{'val':2}, 'right':{'val':3}}
>>> count_nodes(root)
3

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Find the depth (height) of the leftmost path from a node by repeatedly following left children.

If the leftmost depth of the right subtree equals the leftmost depth of the left subtree, then the left subtree is perfect and you can compute its size directly as (2^depth - 1).

If the depths are different, the right subtree is perfect but one level shorter, so you can compute its size directly and recurse on the left subtree.

Use bit shifts (1 << d) to compute powers of two quickly.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.