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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill All Possible Full Binary Trees and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →