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:
Show answer & explanation
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:
- Linear left (all nodes left children)
- Linear right (all nodes right children)
- Root with one left child, that child has right child
- Root with one right child, that child has left child
- Root with two children (one left, one right)