Size of Binary Tree

Time: O(n)

Space: O(h)

Intuition

Tree size means counting how many nodes exist. For every non-null node, count 1 for itself, then recursively count nodes in its left and right subtrees. The recursive decomposition naturally mirrors the tree structure and visits each node exactly once.

Algorithm

1If root is null, return 0.
2Recursively compute leftSize = getSize(root.left).
3Recursively compute rightSize = getSize(root.right).
4Return leftSize + rightSize + 1 for the current node.

Example Walkthrough

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

1.Node 4: left and right are null, so size = 0 + 0 + 1 = 1.
2.Node 5: similarly, size = 1.
3.Node 2: size = size(4) + size(5) + 1 = 1 + 1 + 1 = 3.
4.Node 3: leaf, size = 1.
5.Node 1: size = size(2) + size(3) + 1 = 3 + 1 + 1 = 5.

Output: 5

Common Pitfalls

•Do not forget the +1 for the current node; otherwise you only count descendants.
•Base case must return 0 for null, not 1.
•Deep skewed trees can cause recursion depth issues in constrained environments.

Size of Binary Tree.java

Java

// Approach: Use DFS recursion. Size of a tree = size(left subtree) + size(right subtree) + 1 (current node).
// Base case: null node contributes 0.
// Time: O(n) Space: O(h)
class Node {

    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

    public int getSize(Node root) {
        if (root == null) {
            return 0;
        }
        int leftSize = getSize(root.left);
        int rightSize = getSize(root.right);
        return rightSize + leftSize + 1;
    }
}

Was this solution helpful?