Every Full Binary Tree With n Nodes
Updated
Problem statement
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 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)