← Grammarly Interview Insights

Grammarly·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026Remote

Summary

Phone screen at Grammarly for a software engineer role, three binary tree problems back to back. Nothing crazy in terms of topics but the third one had some teeth to it.

Questions Asked (3)

Q1

Find the maximum depth of a binary tree.

Algorithms & Data Structures
Author's notes

Classic warmup.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the definition of depth (number of nodes vs. edges on the longest path from root to leaf) and the tree's properties (e.g., binary, possibly unbalanced). Then present a recursive DFS solution that computes the max of left and right subtree depths plus one, and optionally mention an iterative BFS alternative. Analyze time and space complexity, and discuss trade-offs.

Pro tip: Mention that recursion depth could cause stack overflow for very deep trees, and offer an iterative BFS solution as a more robust alternative in production code. This shows awareness of real-world constraints beyond just passing tests.

1. Clarify the problem

Ask whether depth is measured in nodes or edges, and confirm the tree is binary and not necessarily balanced. This ensures your solution matches the interviewer's expectations.

2. Choose an approach

Decide between recursive DFS (simpler, elegant) and iterative BFS (avoids recursion limits). Explain your choice based on constraints like tree size and potential stack overflow.

3. Walk through the algorithm

For DFS: if node is null return 0; else return 1 + max(depth(left), depth(right)). For BFS: use a queue and count levels until empty. Verbally trace a small example.

4. Analyze complexity

State that both approaches run in O(n) time and O(h) space for DFS (recursion stack) or O(w) for BFS (queue), where h is height and w is max width. Mention worst-case O(n) space for skewed trees.

5. Discuss edge cases and optimizations

Cover empty tree (depth 0), single node (depth 1), and highly unbalanced trees. Mention that iterative BFS avoids stack overflow and is often preferred in production.

Key Points to Mention

  • Definition of depth: number of nodes on the longest path from root to leaf (or edges, clarify).
  • Recursive DFS solution: depth = 1 + max(depth(left), depth(right)), base case null = 0.
  • Iterative BFS solution: level-order traversal counting levels.
  • Time complexity O(n) and space complexity O(h) for DFS, O(w) for BFS.
  • Trade-offs: recursion simplicity vs. stack overflow risk; BFS uses more memory for wide trees.
  • Edge cases: empty tree, single node, skewed tree.

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

Q2

Given a binary tree, return its level-order traversal as a list of lists, one per level.

Algorithms & Data Structures
Author's notes

BFS with a queue.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use BFS with a queue to traverse the tree level by level. For each level, process all nodes currently in the queue, collect their values, and enqueue their children. This ensures each sublist corresponds to one level.

Pro tip: Mention that you can also solve it with DFS by passing the level index and appending to the appropriate sublist, but BFS is more intuitive and avoids recursion depth issues. This shows you understand trade-offs.

1. Clarify the problem

Confirm the expected output format (list of lists) and edge cases (empty tree, single node). Ask if the tree is balanced or if there are constraints on node values.

2. Choose BFS with a queue

Explain that BFS naturally processes nodes level by level. Initialize a queue with the root and a result list.

3. Process each level

While the queue is not empty, record the current queue size (number of nodes at this level). Iterate that many times: dequeue a node, add its value to the current level list, and enqueue its children.

4. Collect and return results

After processing all nodes at the current level, append the level list to the result. Continue until the queue is empty, then return the result.

5. Analyze complexity

State that time complexity is O(n) since each node is visited once, and space complexity is O(n) for the queue and result in the worst case (e.g., a full level).

Key Points to Mention

  • BFS uses a queue (FIFO) to ensure level-by-level processing.
  • Tracking the number of nodes per level is crucial to separate levels in the output.
  • Edge cases: empty tree returns an empty list; a tree with only a root returns [[root.val]].
  • Time complexity O(n) and space complexity O(n) where n is the number of nodes.
  • Alternative DFS approach with level parameter, but BFS is more straightforward for level-order.
  • Handling null children: only enqueue non-null children to avoid processing nulls.

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

Q3

In a binary tree where each node holds a value 0 to 25 representing letters a through z, find the lexicographically smallest string formed by reading from any leaf up to the root.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This one took me a minute to get oriented.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose a depth-first search (DFS) that traverses from each leaf to the root, building strings and comparing them lexicographically. Optimize by pruning branches where the current path prefix is already lexicographically larger than the best found so far, and discuss time/space complexity trade-offs.

Pro tip: Mention that you can avoid constructing full strings by comparing paths character-by-character during traversal, which reduces memory overhead and early-terminates comparisons. Also, explicitly handle the case of an empty tree or a single-node tree to show thoroughness.

1. Clarify the problem and constraints

Ask about tree size, whether values are guaranteed 0-25, and if the tree can be empty or have a single node. Confirm that 'leaf' means a node with no children.

2. Outline a brute-force approach

Describe a simple DFS that collects all root-to-leaf paths, reverses each to get leaf-to-root strings, and returns the lexicographically smallest. State its O(N * H) time and space complexity.

3. Propose an optimized DFS with pruning

Explain how to traverse from root to leaves while maintaining the current path, and compare the reversed path to the best found so far. Prune branches where the prefix is already lexicographically larger than the best.

4. Analyze complexity and trade-offs

Discuss that the optimized approach still has O(N * H) worst-case time but often performs better due to pruning. Mention that comparing paths character-by-character avoids string concatenation overhead.

5. Test with edge cases

Walk through examples: empty tree, single node, skewed tree, and a tree where multiple leaves yield the same string. Verify the algorithm returns the correct result.

Key Points to Mention

  • Definition of a leaf node and how to identify it during traversal.
  • Lexicographic comparison: shorter string is smaller if it is a prefix of the longer one.
  • DFS vs BFS: DFS is more natural for path construction and pruning.
  • Pruning condition: if current path prefix is greater than the best, skip further exploration.
  • Time complexity: O(N * H) where N is number of nodes and H is height, but can be O(N) with early termination.
  • Space complexity: O(H) for recursion stack, plus O(H) for storing the best string.

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