Size of a Binary Tree

Problem Link

Problem: Size of Binary Tree

Problem Statement

You are given a binary tree. Your task is to find the total number of nodes in the given binary tree.

Examples

Example 1

Input:

       1
     /   \
    2     3

Output: 3

Example 2

Input:

Output: 4

Constraints

1 <= Number of nodes <= 10⁴

Intuition

To compute the size of a binary tree (i.e., number of nodes), we can traverse the entire tree and count each node.
This naturally leads to a recursive approach where the size of the tree is:

Size = 1 (root node) + size(left subtree) + size(right subtree)

Approach (Recursion using Induction – Base Case – Hypothesis)

1. Base Case:

If the node is null, return 0 (size of an empty tree is 0).

2. Hypothesis:

Assume size(left) and size(right) correctly give the number of nodes in the left and right subtrees.

3. Induction:

Return 1 + size(left) + size(right) — counting the current node.

Code (Java)

class Tree {
    // Function to get the size of a binary tree
    int getSize(Node node) {
        // Base case
        if (node == null) return 0;

        // Hypothesis
        int leftSize = getSize(node.left);
        int rightSize = getSize(node.right);

        // Induction
        return 1 + leftSize + rightSize;
    }
}

Time and Space Complexity

Time Complexity: O(N)
Each node is visited exactly once.
Space Complexity: O(H)
Due to recursive stack, where H is the height of the tree (can be O(N) in worst case).

Dry Run

Input:

Recursive stack:

getSize(10)
- getSize(20)
  - getSize(40) → left and right null → returns 1
  - returns 2
- getSize(30) → returns 1
Final: 1 (10) + 2 (20's subtree) + 1 (30) = 4

Conclusion

This is a classic recursion problem that teaches:

How to reduce a tree problem to subtrees (divide and conquer).
How to apply the Induction-Hypothesis-Base Case pattern effectively.