algoadvance

Leetcode 993. Cousins in Binary Tree Sure, let’s go through this problem step-by-step.

Problem Statement:

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

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

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

Clarifying Questions:

1. Can the values x and y be equal?
   • No, the problem states they are two different nodes.
2. What should we return if either x or y is not found in the tree?
   • We should return false.
3. Is it guaranteed that x and y exist in the tree?
   • No, if either doesn’t exist, they can’t be cousins, and we should return false.

Strategy:

1. Perform a Breadth-First Search (BFS) to traverse the tree level-by-level.
2. Keep track of each node’s parent and depth.
3. Once we find both nodes x and y, we check their depths and parents to decide if they are cousins.

Code:

import java.util.LinkedList;
import java.util.Queue;

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

public class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        TreeNode xParent = null, yParent = null;
        int xDepth = -1, yDepth = -1;
        int depth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                if (node.left != null) {
                    queue.offer(node.left);
                    if (node.left.val == x) {
                        xParent = node;
                        xDepth = depth + 1;
                    } else if (node.left.val == y) {
                        yParent = node;
                        yDepth = depth + 1;
                    }
                }

                if (node.right != null) {
                    queue.offer(node.right);
                    if (node.right.val == x) {
                        xParent = node;
                        xDepth = depth + 1;
                    } else if (node.right.val == y) {
                        yParent = node;
                        yDepth = depth + 1;
                    }
                }
            }
            depth++;
        }

        // Check if x and y are cousins
        return xDepth == yDepth && xParent != yParent;
    }
}

Time Complexity:

• O(n): We traverse each node exactly once, where n is the number of nodes in the tree.

Space Complexity:

• O(n): We use a queue to store the nodes for BFS traversal, which in the worst case will store all node at the leaf level, approximately n/2 nodes.

Let me know if there’s anything you need further clarification on!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?