Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026Remote

Summary

Meta SWE coding round, one tree problem the whole time. Pretty standard stuff if you've done your BFS prep, but I fumbled around longer than I should have before landing on the right approach.

Questions Asked (1)

Given the root of a binary tree, write a function to determine whether the tree is a complete binary tree. Return true if it is, false otherwise.

Algorithms & Data Structures

Author's notes

Spent probably two minutes just restating the definition back to myself out loud which felt awkward.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use level-order traversal (BFS) with a queue, tracking whether a null child has been encountered. Once a null is seen, all subsequent nodes must be null; if any non-null node appears after a null, the tree is not complete. Alternatively, assign indices to nodes and check that the maximum index equals the number of nodes minus one.

Pro tip: Clarify the definition of a complete binary tree upfront and discuss edge cases like an empty tree or a single node. Mention that the BFS approach runs in O(n) time and O(n) space, and that the index-based method can be done iteratively with a stack to avoid recursion depth issues.

1. Clarify the problem and edge cases

Confirm that a complete binary tree has all levels filled except possibly the last, which is filled from left to right. Discuss edge cases: empty tree (true), single node (true), and trees with missing children.

2. Choose an approach

Decide between BFS with a flag or index assignment. BFS is straightforward: traverse level by level, and once a null child is seen, no further non-null nodes should appear.

3. Implement the BFS solution

Use a queue to perform level-order traversal. For each node, enqueue its left and right children (including nulls). Maintain a boolean flag that becomes true when a null is encountered; if a non-null node is seen after the flag is set, return false.

4. Analyze complexity and test

State that time complexity is O(n) and space complexity is O(n) in the worst case. Walk through examples: a perfect tree, a tree with a missing left child, and a tree with a node after a null.

5. Discuss alternative approaches

Mention the index-based method: assign index i to a node, left child gets 2i+1, right child gets 2i+2. Track the maximum index and compare with the total number of nodes. This also runs in O(n) time and O(n) space.

Key Points to Mention

Definition of a complete binary tree: all levels except possibly the last are completely filled, and nodes in the last level are as far left as possible.
BFS with a flag to detect if a non-null node appears after a null child.
Time complexity O(n) and space complexity O(n) for both BFS and index-based approaches.
Edge cases: empty tree, single node, and trees with missing children.
Alternative index-based approach: assign indices and check if max index equals n-1.
Avoid recursion for index-based method to prevent stack overflow on deep trees; use iterative stack or queue.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.