ZETA | SDE-2 | Reject | 2025

Round 1 - DSA

Questions: Problem: Given a reference to the root node of a tree, find the number of uni-value subtrees.
Issue: No tree diagram was provided initially and had to ask the interviewer for the diagram, which consumed some time.

Follow-Up 1:
Print the node of the subtree from where the univalue subtree starts.
✅ Successfully solved. Just added 1 printing line.

Follow-Up 2:
Optimize for multiple queries (K queries).
Basically, in the univalueTree Method, the method will be called multiple times, and in the arguments, nodes of the same tree will be passed in K different queries. My original solution was already doing this in O(n * k).
Solve in O(N).
⚠️ This required memoization/pre-computation. The idea was to create an unordered_map<TreeNode*,int> map.
I struggled with implementing it correctly and efficiently within the time limit.

During this Follow-up 2, I asked the interviewer for some kind of hint/something based on my initial implementation. The interviewer had a completely different solution in mind and struggled to grasp how my main approach was working, so I didn’t get any hints here. I think he was expecting a returning count approach from the beginning, which I realized late in the interview. Due to time constraints, I couldn’t implement the final follow-up correctly.

Verdict: ❌ Rejected
Reason: Couldn’t complete the third follow-up in time. He also had 2 more questions planned to ask post completing this, which I got to know in the end.

Here is my solution for the main problem and follow-up 1:

int result = 0;

bool isUniTree(TreeNode* root) {
    if (root == NULL) {
        return true;
    }

    bool isLeftUniTree = isUniTree(root->left);
    bool isRightUniTree = isUniTree(root->right);

    if (root->left != NULL && root->left->val != root->val) {
        return false;
    }
    if (root->right != NULL && root->right->val != root->val) {
        return false;
    }

    if (isLeftUniTree && isRightUniTree) {
        cout << root->val;  // Printing the value of uni-value nodes follow-up1 
        result++;
        return true;
    }
    return false;
}