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

<p>Two nodes of a binary tree are <strong>cousins</strong> if they have the same depth with different parents.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/12/q1248-01.png" style="width: 304px; height: 270px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4], x = 4, y = 3
<strong>Output:</strong> false
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/12/q1248-02.png" style="width: 334px; height: 266px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,4,null,5], x = 5, y = 4
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/13/q1248-03.png" style="width: 267px; height: 258px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,4], x = 2, y = 3
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[2, 100]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
	<li>Each node has a <strong>unique</strong> value.</li>
	<li><code>x != y</code></li>
	<li><code>x</code> and <code>y</code> are exist in the tree.</li>
</ul>


class Solution {
public:
    //  function to find the depth and parent of a given node value
    void findDepthAndParent(TreeNode* node, TreeNode* parent, int depth, int val, int& nodeDepth, TreeNode*& nodeParent) {
        if(node == NULL) return; // base case   
        // If the current node matches the value we're looking for
        if (node->val == val){// current node == x or current node == y 
            nodeDepth = depth; // Set the depth of the node
            nodeParent = parent; // Set the parent of the node
            return; // Return as we found the node
        }
        // recur for the left child
        findDepthAndParent(node->left, node, depth + 1, val, nodeDepth, nodeParent);
        // recur for the right child
        findDepthAndParent(node->right, node, depth + 1, val, nodeDepth, nodeParent);
    }

    // Main function to determine if two nodes are cousins
    bool isCousins(TreeNode* root, int x, int y) {
        if (root==NULL) return false; // If the tree is empty, return false
        //  x and y for finding 
        int xDepth = -1;
        int yDepth = -1; // Initialize depths of x and y
        TreeNode* xParent = NULL; //  parent of x
        TreeNode* yParent = NULL; //  parent of y
        // Find depth and parent for x
        findDepthAndParent(root, NULL, 0, x, xDepth, xParent);
        // Find depth and parent for y
        findDepthAndParent(root, NULL, 0, y, yDepth, yParent);
        // Check if x and y are at the same depth but have different parents
        return (xDepth == yDepth) && (xParent != yParent);
    }
};
13200