← Google Interview Insights

Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Jun 2026

Summary

Google SWE coding round with a tree problem that looked like a BST variant but had a twist I didn't fully appreciate until halfway through. The follow-up about broken trees was where things got interesting.

Questions Asked (2)

Q1

Given the root of a trinary search tree where each node has a left child (values less than current), a middle child (values equal to current), and a right child (values greater than current), find the mode or modes of the tree. Return all values tied for highest frequency.

Algorithms & Data Structures
Author's notes

My first instinct was to just do a full traversal and count with a hashmap, which works, but I kept second-guessing myself thinking they wanted me to exploit the tree structure somehow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Traverse the tree in-order (left, middle, right) to visit nodes in non-decreasing order, which groups equal values together. While traversing, maintain a frequency count for each value and track the maximum frequency and the list of modes. Return the list of modes after traversal.

Pro tip: Clarify whether the tree is balanced or if recursion depth is a concern; an iterative in-order traversal using an explicit stack avoids stack overflow and shows production-level awareness.

1. Understand the problem and clarify constraints

Confirm the definition of mode (most frequent values) and that the tree may have duplicates. Ask about tree size, balance, and whether recursion depth is a concern.

2. Choose traversal method

Decide between recursive and iterative in-order traversal. In-order ensures sorted order, making it easy to count consecutive equal values.

3. Implement traversal with frequency tracking

During traversal, keep track of the current value and its count. When the value changes, compare the count to the maximum frequency and update the modes list accordingly.

4. Handle edge cases and finalize

Consider empty tree, single node, all unique values, and all same values. After traversal, return the list of modes.

5. Analyze complexity and discuss optimizations

State time complexity O(n) and space complexity O(h) for recursion or O(n) for iterative stack. Mention that no extra hash map is needed due to sorted order.

Key Points to Mention

  • In-order traversal of a trinary search tree visits nodes in non-decreasing order, grouping equal values together.
  • Maintain current value, current count, max frequency, and a list of modes during traversal.
  • Update modes when current count exceeds max frequency (reset list) or equals max frequency (append).
  • Time complexity O(n) and space complexity O(h) for recursion or O(n) for iterative stack.
  • Edge cases: empty tree, single node, all unique values, all same values.
  • Avoid using a hash map to count frequencies; exploit the sorted order to achieve O(1) extra space (excluding output).

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

Q2

How would your approach change if the tree structure is broken, meaning nodes may not actually respect the less-than, equal, greater-than ordering constraints?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This one I handled better, weirdly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify what 'broken' means: is it a few violations or completely arbitrary? Then, discuss how to detect violations and adapt algorithms, such as using a brute-force search or rebuilding the tree. Emphasize trade-offs between correctness, time complexity, and practicality.

Pro tip: Mention that in real-world systems, data corruption is often partial, so a hybrid approach (e.g., validate and repair) is more practical than assuming total chaos. Also, relate this to Google's scale: efficient detection and recovery are crucial.

1. Clarify the problem

Ask the interviewer to define the extent of the brokenness: are all nodes violating, or just some? Is the structure still a tree (connected, acyclic)?

2. Detect violations

Explain how to check if the BST property holds, e.g., via in-order traversal or recursive range checks. Discuss time complexity (O(n)) and space.

3. Adapt algorithms

If the tree is broken, standard BST operations (search, insert, delete) may fail. Consider fallback strategies: linear search, rebuilding the tree, or using a different data structure.

4. Discuss trade-offs

Compare approaches: rebuilding costs O(n log n) but restores efficiency; linear search is O(n) per operation but simple. Consider if the tree is static or dynamic.

5. Propose a solution

Recommend a practical approach, such as validating and repairing the tree if violations are few, or switching to a hash table if the structure is unreliable.

Key Points to Mention

  • Definition of a valid BST: left subtree < node < right subtree, with no duplicates (or consistent handling).
  • Detection methods: in-order traversal should yield sorted order; recursive min/max bounds.
  • Impact on operations: search, insert, delete may return incorrect results or fail.
  • Fallback strategies: linear search, rebuilding the tree, or using a balanced tree (e.g., AVL, Red-Black) if insertions are frequent.
  • Trade-offs: time vs. space vs. implementation complexity; rebuilding may be costly but restores O(log n) operations.
  • Real-world considerations: data corruption, concurrent modifications, or malicious input; need for robustness and error handling.

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