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(n) = (2n)! / ((n+1)! × n!). For n=3, C(3) = 6!/(4! × 3!) = 720/(24 × 6) = 5. These five distinct structures represent all possible binary tree topologies with three nodes, regardless of how nodes are arranged within each structure.

Step-by-step Derivation:
Step 1: Recognize that for unlabeled nodes, we count structurally distinct binary trees.
Step 2: Apply the Catalan number formula for n=3: C(3) = (2×3)! / ((3+1)! × 3!) = 6! / (4! × 3!)
Step 3: Calculate: 6! = 720, 4! = 24, 3! = 6
Step 4: C(3) = 720 / (24 × 6) = 720 / 144 = 5
Step 5: The five distinct binary tree structures with 3 nodes are:

  1. Root with left child; left child has left child (linear left)
  2. Root with left child; left child has right child
  3. Root with two children (balanced)
  4. Root with right child; right child has left child
  5. Root with right child; right child has right child (linear right)