Skip to interview prep
Apexed

162. How many structurally different binary trees can be formed with n nodes?

MediumTrees

Technical
Show model answer

Pick how many of the remaining n - 1 nodes go in the left subtree, say i, with n - 1 - i on the right; the shapes multiply and sum over i, giving T(0) = 1 and T(n) = sum of T(i) * T(n - 1 - i). This is the Catalan recurrence, so there are C(n) = (2n)! / ((n + 1)! n!) shapes: 1, 2, 5, 14, 42 for n = 1..5.

If the n nodes carry distinct labels that can be placed anywhere, each shape can be labelled in n! ways, giving n! * C(n) labelled trees. The DP takes O(n²) time; the closed form needs big integers for large n.

How many structurally different binary trees can be formed with n nodes — Data structures & algorithms interview question — Apexed