FastPrepEvery Full Binary Tree With n Nodes
Problems/Every Full Binary Tree With n Nodes

Every Full Binary Tree With n Nodes

Adobe logoAdobe● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This problem lists every full binary tree for a chosen number of nodes. In a full tree, each node has zero or two children. A report by an intern candidate for a software engineering role (posted August 2023, placed on a waiting list that was never confirmed) has it as the coding problem of the first technical interview, which came after an online test. The interviewer first asked which data structure the candidate liked best. On hearing trees, the interviewer gave this task. Talk about its cost, recursion theory and threads followed. The report gives no output form, limits or examples.

Our choices: each tree is returned as a preorder shape code, N for a node with two children and L for a leaf, instead of being printed or built from nodes. The codes are sorted. An even n gives an empty list. n is at most 15. The examples are new.

Our version is about 80% the same as the reported question.

A full binary tree is a binary tree in which every node has either zero or two children. Given n, return every full binary tree with exactly n nodes. Nodes carry no values; only the shape matters.

Write each tree as a shape code: visit it in preorder (the node, then its left subtree, then its right subtree) and write N for a node with two children and L for a leaf. For example, a root with two leaf children is "NLL". Return the codes sorted in increasing string order (L comes before N). If no full binary tree has n nodes, return an empty list.

Function

allFullTrees(n: int) → List<String>

Examples

Example 1

n = 5return = ["NLNLL","NNLLL"]

With 5 nodes the root has two children, and one child is a leaf while the other has two leaf children. Putting the bigger child on the right gives "NLNLL"; on the left gives "NNLLL". In sorted order: ["NLNLL","NNLLL"].

Example 2

n = 4return = []

A full binary tree always has an odd number of nodes (every node with children adds two), so no tree has 4 nodes. Answer: [].

Example 3

n = 1return = ["L"]

A single leaf: ["L"].

Constraints

  • 1 <= n <= 15

More Adobe Phone Screen questions

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
  • Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
  • Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
  • Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
  • Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
  • Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
  • Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
  • Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026

Similar questions at other companies

  • Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
  • House Robber IIIOkta · PHONE SCREENOkta interview questions
  • Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
  • Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
  • House Robber IIIVisa · PHONE SCREENVisa interview questions
  • Construct a Binary Tree from Preorder and InordereBay · PHONE SCREENeBay interview questions
  • Filter Data with Composable PredicatesCoreWeave · PHONE SCREEN
  • Normalize Loan Merchants to Root BusinessesAffirm · PHONE SCREENAffirm interview questions
  • Minimum Root-to-Leaf Cut CostGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Count Uni-Valued SubtreesAmazon · PHONE SCREEN

Interview reports that mention this question

  • Adobe SWE Intern Interviews: 27 Experiences (Part 2 of 4)

Adobe interview experiences

  • Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
  • Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
  • Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
  • Adobe New Grad MTS Interview Questions: 7 Experiences
  • Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)
All Adobe interview questionsSee Adobe hiring insights
Saved
class Solution {
    public List<String> allFullTrees(int n) {
        // Write your code here.
    }
}
Checking account…