A complete binary tree with n non-leaf nodes contains

Concept

In a binary tree where every non-leaf (internal) node has exactly two children -- the convention this classic exam question follows, despite being phrased as a "complete" binary tree -- there is a fixed relationship between the number of non-leaf nodes and the number of leaf nodes: the leaf count always exceeds the non-leaf count by exactly one, regardless of the tree's shape.

Application

1. Start with the smallest such tree: a single node, which is itself a leaf. Here, non-leaf nodes = 0 and leaf nodes = 1, so leaves already equal non-leaf nodes plus one.

2. To grow the tree, pick any leaf and turn it into a non-leaf node by giving it two brand-new leaf children. Call this one operation a "split."

3. Each split removes exactly one leaf (the one just converted) and adds exactly two new leaves, for a net gain of one leaf, while the non-leaf count also increases by exactly one.

4. So after every split, the relationship "leaves = non-leaf nodes + 1" is preserved: it held before the split, and the split increases both sides by exactly one.

5. After n splits starting from the single-node tree, there are exactly n non-leaf nodes and n+1 leaf nodes.

6. Total nodes = non-leaf nodes + leaf nodes = n + (n+1) = 2n+1.

Cross-check

Cross-check with a small worked example: take n = 2. Performing two splits starting from the single-node tree gives 2 non-leaf nodes and 3 leaves, for 5 nodes total, matching 2(2)+1 = 5 -- exactly what a hand-drawn tree of a root with one child further split into two grandchildren also shows.

Note

Note on terminology: this well-known ISRO 2016 Computer Science exam question is phrased as a "complete binary tree," but the intended and universally-published answer (confirmed across multiple independent solved-question sources for this exact exam item) relies on the strict/full binary tree property used above, where every non-leaf node has exactly two children. A tree that is "complete" in the strict textbook sense (every level full except possibly the last, filled left to right) can technically include a node with only one child on the last level, which would break this relationship -- but that stricter reading is not the convention this exam question and its official, widely-published answer key use.