OA. free
Free
Qualcomm Digital Electronics Digital Electronics Medium

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

Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.

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

Choose one option.
Show answer & explanation
Answer: C. 5

The number of structurally distinct binary trees with n unlabeled nodes is given by the nth Catalan number: Cₙ = (2n)! / ((n+1)! × n!). For n=3, C₃ = 6! / (4! × 3!) = 720 / (24 × 6) = 5. These five distinct tree structures represent all possible arrangements of three nodes in a binary tree without labeling constraints.

Step-by-step Derivation:
Using the Catalan number formula for the number of structurally distinct binary trees:

For n = 3 nodes:
Cₙ = (2n)! / ((n+1)! × n!)
C₃ = (2×3)! / ((3+1)! × 3!)
C₃ = 6! / (4! × 3!)
C₃ = 720 / (24 × 6)
C₃ = 720 / 144
C₃ = 5

The five structurally distinct binary trees with 3 unlabeled nodes are:

  1. Linear left (all nodes left children)
  2. Linear right (all nodes right children)
  3. Root with one left child, that child has right child
  4. Root with one right child, that child has left child
  5. Root with two children (one left, one right)