LeetCode 993: Cousins in Binary Tree Solution

Master LeetCode problem 993 (Cousins in Binary Tree), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

993. Cousins in Binary Tree

Easy

Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a depth-first search (DFS) traversal of the binary tree to find the depths and parents of the nodes with values x and y. We keep track of the depth and parent node of each node as we traverse the tree. If the depths of x and y are the same and their parents are different, then they are cousins.

Perform a DFS traversal of the tree while keeping track of the depth and parent node for each node.
If we find nodes with values x and y, we check if they are cousins by comparing their depths and parents.
Return true if they are cousins, false otherwise.

Time complexity: O(n) - We visit each node once. Space complexity: O(n) - The space used by the recursive call stack.

Solution Code

class Solution {
    TreeNode parentX = null;
    TreeNode parentY = null;
    int depthX = -1;
    int depthY = -1;

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return (depthX == depthY) && (parentX != parentY);
    }

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

        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val == y) {
            parentY = parent;
            depthY = depth;
        }

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 993 (Cousins in Binary Tree)?

This page provides optimized solutions for LeetCode problem 993 (Cousins in Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 993 (Cousins in Binary Tree)?

The time complexity for LeetCode 993 (Cousins in Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 993 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 993 in Java, C++, or Python.

Back to LeetCode Solutions