Google Intern Software Engineer Interview Experience — Binary Tree Node-Counting Question

Real question from the 27 intern interview.

It's a binary tree problem: count the nodes that satisfy a condition based on the relationship between the current node's value and the values in its left and right subtrees. The check involves taking one value from the left subtree and one from the right subtree and comparing their sum and their product against the current node's value.

Note that the comparison range is the entire left and right subtrees, not just the direct left and right children.

For the approach, you can use a post-order traversal, maintaining the max, min and count of each subtree during the recursion and then merging the results, which avoids rescanning subtrees. If negative numbers are allowed, you need to take extra care with the product check. It's also a good idea to confirm the leaf node case and the one-sided-subtree case up front.

The overall time complexity can be O(n). It mainly tests tree recursion, information maintenance, and edge-case handling.