← eBay Interview Insights

eBay·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

eBay technical phone screen for a software engineer role, one algorithmic question that looked manageable at first but has enough moving parts to trip you up if you haven't thought carefully about how to track completeness in a single pass.

Questions Asked (1)

Q1

Given a binary tree, count the number of subtrees that are both complete binary trees and have an even sum. Your solution should run in O(n) time using a post-order traversal where each node returns enough state to verify completeness without re-traversing.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The even-sum part is trivial, just propagate sums upward.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order traversal where each recursive call returns a tuple containing the subtree's sum, its height, whether it is complete, and the count of complete subtrees with even sum. At each node, combine the left and right results to determine if the current subtree is complete and compute its sum, incrementing the count if the sum is even. This ensures O(n) time by processing each node once and avoiding redundant traversals.

Pro tip: Emphasize that completeness can be verified in O(1) per node by comparing the heights of left and right subtrees and checking the completeness flags, rather than re-traversing. This demonstrates a deep understanding of tree properties and efficient algorithm design.

1. Define the return state

Decide on the tuple to return from each recursive call: subtree sum, height, completeness flag, and count of valid subtrees. This encapsulates all necessary information for the parent.

2. Base case handling

For a null node, return sum=0, height=0, isComplete=true, and count=0. This provides a neutral starting point for recursion.

3. Post-order traversal and combination

Recursively process left and right children. Compute current sum as left.sum + right.sum + node.val. Determine completeness: left and right must be complete, and either left.height == right.height (left may be perfect) or left.height == right.height + 1 (left is perfect and right is complete).

4. Count valid subtrees

If the current subtree is complete and its sum is even, increment the count. Combine counts from left and right subtrees. Return the updated state to the parent.

5. Final result

After the traversal, the count returned from the root is the total number of complete subtrees with even sum. Return that count.

Key Points to Mention

  • Post-order traversal ensures children are processed before parent, enabling bottom-up state aggregation.
  • Completeness check: A subtree is complete if both children are complete and the height difference is at most 1, with specific conditions on the left and right heights.
  • Even sum check: Sum parity can be tracked by accumulating sums modulo 2 to avoid integer overflow, though full sum is fine for typical constraints.
  • Time complexity O(n) because each node is visited once and state combination is O(1).
  • Space complexity O(h) for recursion stack, where h is tree height; can be O(n) in worst case.
  • Trade-off: Returning multiple values in a tuple may be less elegant than a custom class, but it's efficient and clear.

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