Skip to main content

894. All Possible Full Binary Trees

medium

Return every structurally distinct full binary tree with exactly n nodes (each node has 0 or 2 children). Beautiful demonstration of structural recursion plus memoization on tree shapes — the same Catalan-number recurrence in disguise.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0. Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order. A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Constraints

  • 1 <= n <= 20

Examples

Example 1

Input
n = 7
Output
[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2

Input
n = 3
Output
[[0,0,0]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Full binary trees have an odd number of nodes. If n is even, return [].

Hint 2

Recurse on n: build all trees by splitting n - 1 internal nodes into a left subtree of size L and a right subtree of size R = n - 1 - L (both must be odd).

Hint 3

For each (left subtree, right subtree) pair, create a new root with those children.

Hint 4

Memoize results by n — the same subtree count produces the same set of shapes.

Solution approach

Reveal approach

Recurse on n with memoization keyed by n. Base case: n == 1 -> return a single node tree. If n is even, return []. Otherwise, for L = 1, 3, 5, ..., n - 2 (odd numbers), let R = n - 1 - L. Recursively generate leftTrees = allTrees(L) and rightTrees = allTrees(R). For every (leftRoot, rightRoot) pair, create a new root with val 0, root.left = leftRoot, root.right = rightRoot, and add root to the result. Cache the result by n so subsequent calls with the same size are free. Note: subtrees are shared across results — fine for this problem because val is constant and the test harness doesn't mutate. Time is the Catalan-like number of shapes which grows fast; memoization keeps redundant work out.

Complexity

Time
O(2^n / sqrt(n)) — Catalan-shaped output size
Space
O(2^n / sqrt(n))

Related patterns

  • recursion
  • memoization
  • tree-construction

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Microsoft
  • Google

More Recursion practice problems

See all Recursion problems →