Count Univalue Subtrees

Count Univalue Subtrees

What is this problem about?

The Count Univalue Subtrees interview question focuses on tree structures. A "univalue" subtree is a subtree where every node within it has the same value. Your task is to traverse a given binary tree and return the total count of such subtrees. It is important to remember that a single leaf node is always a univalue subtree.

Why is this asked in interviews?

Google and Bloomberg use this binary tree interview pattern to evaluate a candidate's proficiency with recursion and post-order traversal. It tests your ability to aggregate information from child nodes to make a decision about the parent node. It's an excellent problem for demonstrating clean recursive logic and handling null pointers.

Algorithmic pattern used

This problem is best solved using Depth-First Search (DFS), specifically a Post-order Traversal.

1. Check the left subtree.
2. Check the right subtree.
3. If both subtrees are univalue AND their root values match the current node's value (or if they are null), then the current node's subtree is also univalue. By using a bottom-up approach, you can maintain a running count of valid subtrees.

Example explanation

Imagine a tree: 5 / 1 5 / \
1 1 5

• Leaf nodes (1, 1, 5) are all univalue. Count = 3.
• Subtree rooted at the middle 1 has children 1 and 1. Since all are the same value, it's univalue. Count = 4.
• Subtree rooted at the top 5 (right side) has a child 5. It's univalue. Count = 5.
• The root 5 has left child 1 and right child 5. Values don't match. Root is NOT univalue. Total: 5.

Common mistakes candidates make

• Global Variable Misuse: Using a global counter without resetting it or failing to pass state correctly through recursion.
• Short-Circuit Evaluation: In some languages, check(left) && check(right) might skip check(right) if check(left) is false. You must ensure both subtrees are processed to count their univalue subtrees.
• Null Handling: Not properly identifying that a null child effectively "matches" any parent value for the univalue condition.

Interview preparation tip

When dealing with tree problems where a parent's state depends on its children, always think of post-order traversal. It ensures you have all the necessary information from the bottom before making a conclusion at the top.