← eBay Interview Insights

eBay·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

eBay software engineer interview with a tree problem that looked manageable until I actually had to track three things at once through a post-order traversal. Not the worst session but definitely made me second-guess my recursion instincts.

Questions Asked (1)

Q1

Given a binary tree, count how many subtrees satisfy two conditions simultaneously: the absolute difference between left and right subtree heights is at most 1, and the sum of all node values in the subtree is even.

Algorithms & Data Structures
Author's notes

The two conditions together is what got me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order DFS that returns both the height and the sum of node values for each subtree. At each node, check if the absolute height difference is ≤1 and the sum is even, incrementing a counter if both conditions hold. Return the height and sum upward to enable O(n) time complexity.

Pro tip: Clarify the definition of height (edges vs. nodes) and whether a single node counts as a subtree; handling these edge cases upfront shows attention to detail and avoids off-by-one errors.

1. Clarify definitions and constraints

Ask the interviewer to confirm the definition of height (number of edges or nodes) and whether a leaf node is considered a valid subtree. Also discuss the expected input size to determine if recursion depth is a concern.

2. Design the recursive function

Define a helper function that takes a node and returns a pair: the height of the subtree rooted at that node and the sum of all node values in that subtree. For a null node, return height -1 (if edges) or 0 (if nodes) and sum 0.

3. Process children and check conditions

Recursively call the helper on the left and right children. Compute the current height as 1 + max(leftHeight, rightHeight) and the current sum as node.val + leftSum + rightSum. Check if abs(leftHeight - rightHeight) ≤ 1 and current sum is even; if so, increment a global counter.

4. Return aggregated results

Return the computed height and sum to the parent call. After the recursion completes, the global counter holds the total number of valid subtrees.

5. Analyze complexity and test

State that the algorithm runs in O(n) time and O(h) space due to recursion, where n is the number of nodes and h is the tree height. Walk through a small example to verify correctness.

Key Points to Mention

  • Post-order traversal (DFS) to process children before parent
  • Returning multiple values (height and sum) from each recursive call
  • Global counter or mutable variable to accumulate the count
  • Height definition: edges vs. nodes, and handling of null nodes
  • Even sum check using modulo operator (sum % 2 == 0)
  • Time and space complexity analysis: O(n) time, O(h) space

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