find cousins in a binary tree

Question

I am trying to solve LeetCode problem 993. Cousins in Binary Tree:

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• 1 <= Node.val <= 100
• Each node has a unique value.
• x != y
• x and y are exist [sic] in the tree.

My attempt

I made a height function which returns the height of a node from root and I checked the heights of both X and Y. If they are different I returned false. Then I made a parent function which returns the parent of a node. Then I checked if the parents are same return false else return true.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
int height(TreeNode* root,int x){
    if(root==NULL)
        return -1;
    if(root->val==x)
        return 1;
    int lh=height(root->left,x);
    int rh=height(root->right,x);

    if(lh!=-1)
        return lh+1;
    if(rh!=-1)
        return rh+1;
    
     return -1;
}

TreeNode* parent(TreeNode* root,int x){
    if(!root)
        return NULL;
    if(root->right && root->right->val==x )
        return root;
    if(root->left && root->left->val==x)
        return root;
    TreeNode* lh=parent(root->left,x);
    TreeNode* rh=parent(root->right,x);   
    if(!lh)
        return lh;
    if(!rh)
        return rh;
    
        return NULL;
}

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        //check if height of both are same
        int xh=height(root,x);
        int yh=height(root,y);
        if(xh!=yh)
            return 0;

        ///check if parents of both are same
        TreeNode* xp=parent(root,x);
        TreeNode* yp=parent(root,y);
        if(xp==yp)
            return 0;
        
        return 1;
    }
};

Problem

I get the wrong result for this example input:

• Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
• Expected Output: true

... but my code returns false. Where is my mistake?

Answer 1

You have a mistake in the parent function.

This group of statements will always return NULL:

    if(!lh)
        return lh;
    if(!rh)
        return rh;
    
        return NULL;

You'll want to return a Node reference when it is not NULL. So correct to this:

    if (lh)
        return lh;
    if (rh)
        return rh;
    
    return NULL;