Complete Binary Trees MCQs: 12 Solved Questions on Height, Leaves and Tree Properties

Work through 12 binary-tree MCQs, then use each explanation to separate rules for arbitrary, complete, full and perfect trees.

KnowledgeGate Team

Exam prep & CS education

Updated 27 Oct 20268 min read
Complete Binary Trees MCQs: 12 Solved Questions on Height, Leaves and Tree Properties

Binary-tree MCQs often hinge on one convention or identity. Test the boundary between arbitrary and complete trees, then use the GATE CS Exam Preparation Courses & Test Series page for broader preparation.

1. Complete binary tree rules to fix before you attempt the set

A complete binary tree fills every level except possibly the last, whose nodes are left-packed. In a full tree, every node has zero or two children; in a perfect tree, every internal node has two children and all leaves share a depth. None of these shape rules implies BST ordering; see Binary Trees and Binary Search Trees.

Here height counts edges, so a single-node tree has height 0. An arbitrary height-h binary tree has from h + 1 to 2^(h+1) - 1 nodes. A complete height-h tree instead has from 2^h to 2^(h+1) - 1 nodes because levels 0 through h - 1 are full.

2. Height and maximum-node MCQs

Question 1

Let H, I, L, and N represent height, number of internal nodes, number of leaf nodes, and the total number of nodes respectively in a rooted binary tree. Which of the following statements is/are always TRUE?

  • (a) L <= I + 1

  • (b) H + 1 <= N <= 2^(H+1) - 1

  • (c) H <= I <= 2^H - 1

  • (d) H <= L <= 2^(H-1)

Answer: (a), (b) and (c). Open Question 1 in the practice bank.

Let n0, n1 and n2 count nodes with zero, one and two children. Since n0 = n2 + 1, L <= I + 1. A height-H path gives the lower bounds in (b) and (c); perfect trees give the upper bounds. Statement (d) fails at H = 2 because four leaves exceed 2^(H-1) = 2. A complete tree also requires N >= 2^H.

Question 2: GATE 2015, Set 1

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

  • (a) 63 and 6, respectively

  • (b) 64 and 5, respectively

  • (c) 32 and 6, respectively

  • (d) 31 and 5, respectively

Answer: (a). Open Question 2 in the practice bank.

Height 5 spans levels 0 through 5. Filling them gives 1 + 2 + 4 + 8 + 16 + 32 = 63 nodes; a chain gives 6. A complete tree of height 5 would have at least 2^5 = 32 nodes.

Question 3: GATE 2007

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

  • (a) 2^h - 1

  • (b) 2^(h-1) - 1

  • (c) 2^(h+1) - 1

  • (d) 2^(h+1)

Answer: (c). Open Question 3 in the practice bank.

Filling levels 0 through h gives the geometric sum 2^0 + ... + 2^h = 2^(h+1) - 1. This maximum is the same for arbitrary and complete binary trees; completeness changes the minimum, not the maximum.

Question 4

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. The appropriate expressions for the two boxes B1 and B2 are

  • (a) B1: (1 + height(n -> right)) B2: (1 + max(h1, h2))

  • (b) B1: (height(n -> right)) B2: (1 + max(h1, h2))

  • (c) B1: height(n -> right) B2: max(h1, h2)

  • (d) B1: (1 + height(n -> right)) B2: max(h1, h2)

Pseudocode for a recursive height function on a binary tree, with two blank boxes labelled B1 and B2 to be filled in.

Answer: (a). Open Question 4 in the practice bank.

Because NULL returns -1, a leaf has height 0. A right-only node needs 1 + height(n -> right); with two children, use 1 + max(h1, h2). A complete tree cannot contain a right-only node because its last level is left-packed.

3. Leaf, internal-node and degree identities

Question 5: GATE 2006, Information Technology

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

  • (a) 10

  • (b) 11

  • (c) 12

  • (d) 15

Answer: (b). Open Question 5 in the practice bank.

The identity n0 = n2 + 1 ignores degree-1 nodes, so L = 10 + 1 = 11. The 25 child edges also equal 5 + 2(10). A complete tree on n nodes has the stronger result L = ceil(n / 2).

Question 6: GATE 2010

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

  • (a) 0

  • (b) 1

  • (c) (n - 1) / 2

  • (d) n - 1

Answer: (a). Open Question 6 in the practice bank.

Each rooted subtree has odd size. A one-child node would have size 1 + odd, which is even, so no node has exactly one child. A complete tree has one one-child node when n is even and none when n is odd; therefore a complete tree satisfying this condition must have odd n.

Question 7

A complete binary tree has 1000 nodes. Its levels fill from the top down and each level fills from the left. How many of its nodes are leaves?

  • (a) 499

  • (b) 500

  • (c) 501

  • (d) 512

Answer: (b). Open the binary-tree practice set.

Number the nodes 1 to 1000 in level order, which is the array form of a complete tree. Node i has a left child exactly when 2i <= 1000, so nodes 1 to 500 are internal and the remaining 500 are leaves. A complete binary tree on n nodes therefore has ceil(n / 2) leaves.

Question 8: GATE 2014, Set 3

DoSomething() receives the root of an arbitrary tree stored in leftmost-child, right-sibling form:

c
typedef struct treeNode *treeptr;

struct treeNode {
    treeptr leftMostChild;
    treeptr rightSibling;
};

int DoSomething(treeptr tree) {
    int value = 0;
    if (tree != NULL) {
        if (tree->leftMostChild == NULL)
            value = 1;
        else
            value = DoSomething(tree->leftMostChild);
        value += DoSomething(tree->rightSibling);
    }
    return value;
}

When the root pointer is passed to DoSomething(), the returned value corresponds to the

  • (a) number of internal nodes in the tree.

  • (b) height of the tree.

  • (c) number of nodes without a right sibling in the tree.

  • (d) number of leaf nodes in the tree.

Answer: (d). Open Question 8 in the practice bank.

A node contributes 1 when leftMostChild == NULL, so it is a leaf. Recursion totals those contributions across children and siblings. Completeness needs a separate level-order check with no node after the first gap.

4. Recursive C function traces

Question 9: GATE 2007

Consider this C program segment, where CellNode represents a node in a binary tree:

c
struct CellNode {
    struct CellNode *leftChild;
    int element;
    struct CellNode *rightChild;
};

int GetValue(struct CellNode *ptr) {
    int value = 0;
    if (ptr != NULL) {
        if (ptr->leftChild == NULL && ptr->rightChild == NULL)
            value = 1;
        else
            value = GetValue(ptr->leftChild) + GetValue(ptr->rightChild);
    }
    return value;
}

What does GetValue() return when ptr points to the root of a binary tree?

  • (a) the number of nodes in the tree

  • (b) the number of internal nodes in the tree

  • (c) the number of leaf nodes in the tree

  • (d) the height of the tree

Answer: (c). Open Question 9 in the practice bank.

NULL returns 0, each leaf returns 1, and an internal node sums its subtrees. The final value is therefore the leaf count. On a complete binary tree with n nodes, this function returns ceil(n / 2).

Question 10

Consider the C function foo and the binary tree shown.

c
typedef struct node {
    int val;
    struct node *left, *right;
} node;

int foo(node *p) {
    int retval;
    if (p == NULL)
        return 0;
    retval = p->val + foo(p->left) + foo(p->right);
    printf("%d ", retval);
    return retval;
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?

  • (a) 3 8 5 13 11 10

  • (b) 3 5 8 10 11 13

  • (c) 3 8 16 13 24 50

  • (d) 3 16 8 50 24 13

Binary tree with root 10, left child 5 holding 3 and 8, and right child 11 holding only 13.

Answer: (c). Open Question 10 in the practice bank.

Printing occurs after both child calls, so values appear in postorder as subtree sums: 3, 8, 5 + 3 + 8 = 16, 13, 11 + 13 = 24, and 10 + 16 + 24 = 50. The pictured tree is not complete because node 11 has a right child but no left child; the postorder-sum trace is still valid.

5. Tree shape and representation questions

Question 11: GATE 2007

The maximum number of binary trees that can be formed with three unlabeled nodes is:

  • (a) 1

  • (b) 5

  • (c) 4

  • (d) 3

Answer: (b). Open Question 11 in the practice bank.

The Catalan count is C3 = binomial(6, 3) / 4 = 20 / 4 = 5. Unlabeled nodes add no label permutations. Of those five shapes, only the root with two children is complete.

Question 12: GATE 2000

Consider the following nested representation of binary trees: (X Y Z) indicates that Y and Z are the left and right subtrees, respectively, of node X. Note that Y and Z may be NULL or further nested. Which of the following represents a valid binary tree?

  • (a) (1 2 (4 5 6 7))

  • (b) (1 (2 3 4) 5 6) 7)

  • (c) (1 (2 3 4) (5 6 7))

  • (d) (1 (2 3 NULL) (4 5))

Answer: (c). Open Question 12 in the practice bank.

Every non-NULL parenthesised tree needs three components: root, left subtree and right subtree. Only (c) follows that rule recursively; it is also perfect and therefore complete. Next, learn to Construct a Binary Tree from Traversals.

6. Complete binary tree traps and retry plan

Do not confuse edge height with level count, complete with full, or a maximum-node formula with an exact count. In recursive code, inspect the base case before tracing upward. If you missed Questions 1, 4, 5 or 10, redo them without the solutions. Then try Binary Tree MCQs: 11 Solved BST, AVL, Heaps (GATE).

7. The short version and next practice step

Check the height convention, use n0 = n2 + 1 where applicable, and trace recursion from its base case. For structured Data Structures practice, use GATE Guidance by Sanchit Sir, then retry every missed question unaided.