Binary Tree Properties MCQs: 12 Solved Questions with Explanations

Binary-tree questions mix child count with graph degree and edge height with levels. Attempt these 12 MCQs before reading the explanations. The GATE CS Exam Preparation collection provides broader data-structures practice.

Binary tree formulas and one worked tree

Here height is measured in edges, so a height-h tree has h + 1 levels:

• edges = n - 1

• A binary-tree node has 0, 1 or 2 children.

• n0 = n2 + 1, where n0 and n2 count nodes with zero and two children.

• Maximum nodes at height h = 2^(h+1) - 1; minimum = h + 1.

• C_n = (1/(n+1)) binom(2n,n) structurally different binary trees exist on n unlabeled nodes.

Use this tree: A has children B, C; B has D, E; C has left child F; and E has left child G. Its leaves are {D, F, G}, two-child nodes {A, B}, and height 3. Thus n0 = n2 + 1 becomes 3 = 2 + 1. See this earlier Binary Tree MCQs collection for mixed practice across traversals, BSTs, AVL trees and heaps. The worked tree here stays focused on structural identities and height.

Binary tree structure and Catalan counting: Questions 1 to 3

Question 1: CoCubes 2023

Which of the following is true about binary trees?

• A. Every binary tree is either complete or full.

• B. Every complete binary tree is also a full binary tree.

• C. Every perfect binary tree is both complete and full.

• D. No binary tree is both complete and full.

Correct answer: C. Every perfect binary tree is both complete and full.

A perfect tree fills every level and gives each internal node two children, so it is complete and full. A complete tree need not be full.

Question 2: 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))

Correct answer: C. (1 (2 3 4) (5 6 7)).

Each non-null tuple needs three fields: root, left and right. Only C consists of a root and two valid subtree triples; the other forms are malformed.

Question 3: 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

Correct answer: B. 5.

C_3 = (1/4) x binom(6,3) = 5: four oriented chains and one root with two children. Unlabeled nodes introduce no 3! factor.

Leaves, child counts and graph degree: Questions 4 to 6

Question 4: GATE 1995

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is

• A. log base 2 of n

• B. n - 1

• C. n

• D. 2^n

Correct answer: B. n - 1.

Degree here means child count. Since n0 = n and n0 = n2 + 1, we get n2 = n - 1; one-child nodes do not affect this identity.

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

Correct answer: B. 11.

Set n2 = 10; then n0 = n2 + 1 = 11. The five one-child nodes do not affect this identity.

Question 6: GATE 2008, Information Technology

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors.

n3 can be expressed as

• A. n1 + n2 - 1

• B. n1 - 2

• C. [((n1 + n2)/2)]

• D. n2 - 1

Correct answer: B. n1 - 2.

Degree now counts every neighbour. Combining the degree sum n1 + 2n2 + 3n3 = 2(n - 1) with n = n1 + n2 + n3 gives n3 = n1 - 2.

Height bounds and recursive height code: Questions 7 to 9

Question 7: 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)

Correct answer: C. 2^(h + 1) - 1.

Height h spans levels 0 through h. A full set of levels contains 1 + 2 + ... + 2^h = 2^(h+1) - 1 nodes.

Question 8: 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

Correct answer: A. 63 and 6, respectively.

With edge height 5, a perfect tree has 2^6 - 1 = 63 nodes, while a five-edge chain has 6. Both calculations require six levels.

Question 9: GATE 2004

Consider the following C program segment

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

int DoSomething(struct CellNode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

• A. The number of leaf nodes in the tree

• B. The number of nodes in the tree

• C. The number of internal nodes in the tree

• D. The height of the tree

Correct answer: D. The height of the tree.

A leaf returns 0; each parent adds one and keeps the larger child result. This is the longest root-to-leaf path in edges, which is 3 in the worked tree above.

Recursive leaf counts and a parity condition: Questions 10 to 12

Question 10: GATE 2007

Consider the following C program segment where CellNode represents a node in a binary tree:

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 = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

• 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

Correct answer: C. the number of leaf nodes in the tree.

NULL contributes 0, each leaf contributes 1, and every internal node adds its subtree results. The worked tree above therefore returns 2 + 1 = 3 leaves.

Question 11: 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

Correct answer: A. 0.

A one-child node over an odd-sized subtree would have 1 + (2k + 1) = 2k + 2 descendants, contradicting the odd-descendant condition. Therefore no node has exactly one child.

Question 12: GATE 2014, Set 3

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

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

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function 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.

Correct answer: D. number of leaf nodes in the tree.

leftMostChild enters a child list and rightSibling scans it. A node without a leftmost child is an original-tree leaf and contributes 1; recursion sums those contributions.

Binary tree MCQ traps and how exams test them

For reconstruction questions, validate the notation before asking whether traversals determine a unique tree. This guide to constructing a binary tree from traversals explains why preorder plus postorder need not identify an arbitrary binary tree uniquely.

Classify misses by range: Q1-Q3 test shape and Catalan counting; Q4-Q6 degree identities; Q7-Q9 height and recursive maximums; Q10-Q12 recursive accumulation and representation tracing.

Binary tree properties: the short version and next practice step

Before calculating, define height and degree. For code, find the base case and whether recursion adds or takes a maximum.

Review the rule behind each miss, then retry the set. Continue with GATE Guidance by Sanchit Sir for lessons or the GATE Test Series for timed practice.