The challenge
Count nodes faster than a full scan when the binary tree is complete.
All levels before the last are full, and the final level fills left to right. Completeness is a required precondition, not checked here.
Example
Perfect example: 7 nodes. Partial final level example: 6 nodes.
Use the walkthrough below to inspect the input and each state change.
See Complete tree count, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
In a complete tree, equal extreme heights prove that the subtree is perfect.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def count_complete(root):
if root is None:
return 0
left, right, lh, rh = root, root, 0, 0
while left:
lh += 1
left = left.left
while right:
rh += 1
right = right.right
if lh == rh:
return (1 << lh) - 1
return 1 + count_complete(root.left) + count_complete(root.right)
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
long long count_complete(Node* root) {
if (!root) return 0;
Node *left = root, *right = root;
int lh = 0, rh = 0;
while (left) { ++lh; left = left->left; }
while (right) { ++rh; right = right->right; }
if (lh == rh) return (1LL << lh) - 1;
return 1 + count_complete(root->left) + count_complete(root->right);
}