Problem Statement

Given a binary tree and two integers x and y, determine if the nodes with values x and y are cousins.

Definition of cousins:

• Nodes are at the same depth in the tree.
• Nodes have different parents.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Explanation: Node 4 is at depth 2, node 3 is at depth 1 → not cousins

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Explanation: Both nodes at depth 3, different parents → cousins

Constraints:

• Number of nodes in the tree: 2 ≤ n ≤ 100
• Each node has a unique value.

---

Approach to Solve the Problem (Simple Language)

We need to check two conditions for nodes x and y:

1. Same depth: Both nodes must be on the same level.
2. Different parents: Nodes cannot have the same parent.

Steps:

1. Traverse the tree using DFS or BFS.
2. While traversing, keep track of:
   • The parent of each node.
   • The depth of each node.
3. After finding both nodes:
   • Check if their depths are equal.
   • Check if their parents are different.
4. Return true if both conditions are satisfied; otherwise, false.

Why DFS works:

• DFS allows tracking the depth and parent while traversing.
• As soon as both nodes are found, we can stop recursion.

---

Java Code Solution (DFS)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class CousinsInBinaryTree {

    private TreeNode xParent = null;
    private TreeNode yParent = null;
    private int xDepth = -1;
    private int yDepth = -1;

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return (xDepth == yDepth) && (xParent != yParent);
    }

    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) return;

        if (node.val == x) {
            xParent = parent;
            xDepth = depth;
        } else if (node.val == y) {
            yParent = parent;
            yDepth = depth;
        }

        dfs(node.left, node, depth + 1, x, y);
        dfs(node.right, node, depth + 1, x, y);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(5);

        CousinsInBinaryTree solution = new CousinsInBinaryTree();
        boolean result = solution.isCousins(root, 5, 4);
        System.out.println("Are nodes cousins? " + result); // Output: true
    }
}

---

Dry Run Example

Input Tree:

       1
      / \
     2   3
      \    \
       4    5
x = 5, y = 4

Step-by-step Execution (DFS):

1. Start DFS at root (1), depth = 0, parent = null
2. Go left → node 2, depth = 1, parent = 1
3. Go left → null → return
4. Go right → node 4, depth = 2, parent = 2
   • Found y = 4 → yParent = 2, yDepth = 2
5. Backtrack to root → go right → node 3, depth = 1, parent = 1
6. Go left → null → return
7. Go right → node 5, depth = 2, parent = 3
   • Found x = 5 → xParent = 3, xDepth = 2
8. Check conditions:
   • xDepth = yDepth = 2 ✅
   • xParent != yParent (3 != 2) ✅
9. Return true → nodes are cousins

---

Textual Diagram for Understanding

Tree:
       1
      / \
     2   3
      \    \
       4    5

Node 4: depth=2, parent=2
Node 5: depth=2, parent=3
Cousin check:
Depth equal? yes
Parent different? yes
→ Result: true

---

Complexity Analysis

• Time Complexity: O(n)
  • We visit each node once.
• Space Complexity: O(h)
  • Recursive DFS stack, h = height of the tree.