EasyBinary SearchBit ManipulationTreeBinary Tree

Count Complete Tree Nodes

1 approach, code in every language

You are given the root of a complete binary tree. In a complete tree every level is fully filled except possibly the last, and the last level is packed as far left as possible.

Return the total number of nodes. A plain traversal is O(n); the goal here is to exploit the completeness property to do better.

Example 1

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

Output: 6

The tree has two full levels plus two extra nodes on the last level.

Example 2

Input: root = [1]

Output: 1

A single root node counts as one.

Constraints

The number of nodes in the tree is in the range [0, 5 * 10^4].
0 <= Node.val <= 5 * 10^4
The tree is guaranteed to be complete.

Left/Right Spine Heights with Perfect-Subtree Shortcut

Measure the leftmost and rightmost path lengths; equal heights mean a perfect subtree counted by a formula, otherwise recurse.

Loading animation…

Intuition

Walking straight down the left edge of a complete tree gives the height along the shortest-filled side, and walking straight down the right edge gives the height along the possibly-shorter side. If those two heights match, the subtree is perfect and packs exactly 2^h - 1 nodes, which we compute instantly with a bit shift. If they differ, the last level is only partially filled, so we recurse into both children and add one for the current node. The key win is that each recursive call collapses at least one branch into the O(1) formula, so the recursion depth is O(log n) and each level costs O(log n) to measure a spine. That yields O(log^2 n) work overall instead of touching every node.

Algorithm walkthrough

1If the node is null, return 0.
2Walk only left children counting steps to get leftHeight, then walk only right children to get rightHeight.
3If leftHeight == rightHeight, the subtree is perfect: return (1 << leftHeight) - 1.
4Otherwise the last row is partial, so return 1 + countNodes(left) + countNodes(right).
5Each recursion resolves one side by formula, giving O(log n) recursive calls.
6Multiplying the O(log n) spine measurement by O(log n) recursion depth gives O(log^2 n).

Implementation

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left_height = 0
        node = root
        while node:
            left_height += 1
            node = node.left

        right_height = 0
        node = root
        while node:
            right_height += 1
            node = node.right

        if left_height == right_height:
            return (1 << left_height) - 1

        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Time

O(log^2 n)

Space

O(log n)

There are O(log n) recursive levels, and each measures a spine in O(log n); the recursion stack is O(log n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Counting the Chute Junctions is our own problem on the technique behind Count Complete Tree Nodes: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free