Count Complete Tree Nodes

LeetCode 222 | Difficulty: Easy

Easy

Problem Description

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

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, 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.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

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**.

Topics: Binary Search, Bit Manipulation, Tree, Binary Tree

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 104 ms)

Metric	Value
Runtime	104 ms
Memory	42.5 MB
Date	2022-01-14

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode left = root, right = root;
        int height = 0;
        while(right != null)
        {
            left = left.left;
            right = right.right;
            height++;
        }
        if(left == null) return (1<<height) - 1;
        return 1 + CountNodes(root.left) + CountNodes(root.right);
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Precisely define what the left and right boundaries represent, and the loop invariant.