Count Complete Tree Nodes

LeetCode Problem #222 (Medium)

Problem Statement

Given a complete binary tree, count the number of nodes.

Testcase

Example 1:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

Prerequisite Knowledge

Complete Binary Tree

Definition of a complete binary tree from Wikipedia: In a complete binary tree 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 2h nodes inclusive at the last level h.

In a complete binary tree, every level must be completely filled. That is, every node starting from the root node must have exactly two children. The only exception to this rule is that the last level of the binary tree may be incomplete. However, the nodes in the last level must be filled from left to right. Therefore, the leaf nodes of the complete binary tree must always lean left.

Source: https://www.programiz.com/dsa/complete-binary-tree

In the image above, we can see that the binary tree has three levels.

The first level contains one node, which is is the root node, marked by the number 1.

The root node has exactly two children which form the second level of the binary tree, marked by 2 and 3 respectively.

The third level contains only three elements instead of the maximum capacity of four. This is allowed in a complete binary tree as the third level contains the leaf nodes of the tree. However, we can see that the leaf nodes have been filled from left to right.

Node 2 has exactly two children, marked by 4 and 5. Node 3 has only one child, marked by 6.

Algorithm

Recursive Approach

1. If the tree is empty, return 0 as the number of nodes.

2. Recursively traverse through each branch of the complete binary tree and calculate the number of nodes in each branch.

3. Add 1 to the number of nodes found in the left and right branches to account for the root node and return this value as the total number of nodes in the complete binary tree.

Code

int countNodes(TreeNode* root) {
    // Recursively calculate the number of nodes in each branch
    return (root == NULL) ? 0 : (1 + countNodes(root->left) + countNodes(root->right));
}