What is the time complexity of Cousins in Binary Tree?

The optimal solution has a time complexity of O(N).

What data structures are used to solve Cousins in Binary Tree?

This problem uses Tree, Depth-First Search, Breadth-First Search, Binary Tree. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Cousins in Binary Tree?

Insight 1: The core definition of cousins involves two conditions: same depth and different parents. Both must be checked. Insight 2: Either Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to traverse the tree and find the depth and parent of the target nodes.

Which companies ask LeetCode 993. Cousins in Binary Tree in interviews?

This problem is frequently asked at Tekion.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Cousins in Binary Tree - LeetCode 993 Solution

Cousins in Binary Tree - Complete Solution Guide

Cousins in Binary Tree is LeetCode problem 993, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 . Example 1: Input: root = [1,2,3,4], x = 4, y = 3 Output: false Example

Detailed Explanation

The problem asks us to determine if two nodes, 'x' and 'y', in a binary tree are cousins. Two nodes are considered cousins if they are at the same depth in the tree but have different parents. The tree is guaranteed to have unique values for each node, and both 'x' and 'y' are guaranteed to exist in the tree. The task is to return 'true' if 'x' and 'y' are cousins, and 'false' otherwise.

Solution Approach

The provided solutions utilize either DFS or BFS to traverse the binary tree, searching for the nodes with values 'x' and 'y'. During the traversal, the algorithm keeps track of the depth and parent of each node visited. Once 'x' and 'y' are found, their depths and parents are compared. If the depths are equal and the parents are different, the nodes are cousins, and the function returns 'true'. Otherwise, it returns 'false'.

Step-by-Step Algorithm

Step 1: Initialize variables to store the parent and depth of nodes x and y. The initial values are set to default values to indicate that the nodes haven't been found yet.
Step 2: Traverse the tree using either DFS or BFS. For DFS, a recursive function is used. For BFS, a queue is used.
Step 3: During traversal, for each node, check if its value matches x or y. If a match is found, update the parent and depth accordingly.
Step 4: For BFS approach, after processing each level, check if both x and y have been found. If so, break from the loop to improve efficiency.
Step 5: After the traversal is complete (or after breaking out of the loop), compare the depths and parents of x and y.
Step 6: If the depths are equal and the parents are different, return true. Otherwise, return false.

Key Insights

Insight 1: The core definition of cousins involves two conditions: same depth and different parents. Both must be checked.
Insight 2: Either Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to traverse the tree and find the depth and parent of the target nodes.
Insight 3: The algorithm can terminate early once both nodes x and y are found, improving efficiency.

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(H)

Topics

This problem involves: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Companies

Asked at: Tekion.

Cousins in Binary Tree | LeetCode 993

Easy

Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(N)Space: O(H)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        int xDepth = -1;
        int yDepth = -1;
        TreeNode xParent = null;
        TreeNode yParent = null;

        java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
        java.util.Queue<Integer> depthQueue = new java.util.LinkedList<>();

        queue.offer(root);
        depthQueue.offer(0);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int depth = depthQueue.poll();

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

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

            if (xDepth != -1 && yDepth != -1) {
                break;
            }
        }

        return xDepth == yDepth && xParent != yParent;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 993: Cousins in Binary Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Companies

Tekion

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:993

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize variables to store the parent and depth of nodes x and y. The initial values are set to default values to indicate that the nodes haven't been found yet.
2
Step 2: Traverse the tree using either DFS or BFS. For DFS, a recursive function is used. For BFS, a queue is used.
3
Step 3: During traversal, for each node, check if its value matches x or y. If a match is found, update the parent and depth accordingly.
4
Step 4: For BFS approach, after processing each level, check if both x and y have been found. If so, break from the loop to improve efficiency.
5
Step 5: After the traversal is complete (or after breaking out of the loop), compare the depths and parents of x and y.
6
Step 6: If the depths are equal and the parents are different, return true. Otherwise, return false.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N)

💾

Space Complexity

O(H)

📝

Why?

The time complexity is O(N) because, in the worst case, we might have to visit all nodes to find x and y. The space complexity for BFS arises from the queue which can contain at most all nodes at a single level (the width). For DFS, the space complexity arises from the call stack, which grows proportionally to the height of the tree in the worst-case (skewed tree).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Depth-First Search

Instead of recursive DFS, we can use a stack to implement iterative DFS. This avoids potential stack overflow issues for very deep trees.

Time: O(N)Space: O(H) or O(W), depending on implementation details.

Trade-offs: Iterative DFS might be slightly more complex to implement than recursive DFS, but it provides better control over the stack and avoids stack overflow issues. Iterative DFS with stack will be using the maximum width of the tree in the worst case and H (height of the tree) in the best case where H is O(logN).

✨

Key Insights

1Insight 1: The core definition of cousins involves two conditions: same depth and different parents. Both must be checked.
2Insight 2: Either Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to traverse the tree and find the depth and parent of the target nodes.
3Insight 3: The algorithm can terminate early once both nodes x and y are found, improving efficiency.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: `root` is null. While the problem statement constraints guarantee at least two nodes, handling a null `root` is good practice. The C++ and C solutions explicitly handle this case by returning `false` if `root` is null. The other solutions implicitly handle it as well when `root` is null since the traversal doesn't take place.
Edge case 2: `x` or `y` not found. The problem states that both `x` and `y` are guaranteed to be present. Therefore, no explicit checks are required, but checking for `xDepth == -1` or `yDepth == -1` after the traversal could provide robustness.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly checking for cousins by only verifying that they have different parents but failing to check that they are at the same depth.

✗Common mistake 2: Assuming that finding 'x' and 'y' on the same level automatically makes them cousins. They could be siblings if they share the same parent.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing organizational charts. Determining if two employees are at the same hierarchical level but in different departments (reporting to different managers) is analogous to finding cousins in a tree.

🏦Real-world scenario 2: Social networking analysis. Identifying users who are 'friends of friends' (same level of connection) but are not directly connected (different immediate friends - parent nodes).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 2, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

What is the difference between DFS and BFS for trees?

DFS (using recursion or stack) explores depth-first, useful for path-finding and backtracking problems. BFS (using queue) explores level-by-level, ideal for finding shortest paths or processing nodes by depth. Choose based on whether level information matters.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Cousins in Binary Tree"?

For this easy-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?