Count Complete Tree Nodes - Practice Coding Problems

Count Complete Tree Nodes - Problem

Given the root of a complete binary tree, return the number of 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.

Input & Output

Example 1 — Complete Binary Tree

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

› Output: 6

💡 Note: All levels are filled except the last level has 3 out of 4 possible nodes, total count is 6

Example 2 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Tree has only root node, so count is 1

Example 3 — Perfect Binary Tree

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

› Output: 7

💡 Note: All levels are completely filled, total 7 nodes in perfect binary tree

Constraints

The number of nodes in the tree is in the range [1, 2 × 10⁴]
1 ≤ Node.val ≤ 5 × 10⁴
The tree is guaranteed to be complete

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Complete binary tree with nodes filled left-to-right

Smart Counting

Use complete tree properties instead of visiting each node

Result

Total count calculated efficiently

Key Takeaway

🎯 Key Insight: Use the complete binary tree property to count nodes efficiently with binary search instead of traversing every node

Asked in

G Google 12 f Facebook 8 a Amazon 6 M Microsoft 5

The key insight is leveraging the complete binary tree property to avoid visiting every node. The optimal approach uses binary search on the last level combined with path existence checking to achieve O(log² n) time complexity instead of the naive O(n). Best approach: Binary Search - Time: O(log² n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(n)	O(h)	Visit every node using depth-first search to count them
Binary Search on Last Level	O(log² n)	O(log n)	Use binary search to count nodes in the last level efficiently

Brute Force DFS — Algorithm Steps

Step 1: Start from root node
Step 2: Recursively visit left and right subtrees
Step 3: Return 1 + left_count + right_count

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at Root

Begin traversal at root node

Visit All Nodes

Recursively visit left and right subtrees

Count Total

Sum up all visited nodes: 1 + left + right

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int solution(struct TreeNode* root) {
    if (!root) return 0;
    return 1 + solution(root->left) + solution(root->right);
}

struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Simplified for demo - assume input [1,2,3,4,5,6] represents complete tree
    struct TreeNode* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    
    int result = solution(root);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit every node exactly once in the tree

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler