Cousins In Binary Tree LeetCode Java | LeetCode 993 | Programming Tutorials

Показать описание

Cousins In Binary Tree LeetCode Solution using Java. In this tutorial, I have explained how to find cousins in a binary tree using Level Order Traversal (BFS) and Depth First Search (DFS).

Given two values x and y, we have to write a code to check the nodes corresponding to values x and y are cousins or not. All the values in this binary tree are unique.

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

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

This problem is LeetCode Problem 169 known as Cousins in Binary Tree.

Рекомендации по теме

Комментарии

Thanks, your explanation was easy to follow.

rtpforever

Great again! Love the fact you provide several approaches. Please keep doing this in future too. 🔥

pahehepaa

Time complexity of below approach is logn as I am doing depth first search

praveenj

I have solved this problem in leetcode challenges today
below is my accepted solution :
*/
class Solution {

int level=Integer.MIN_VALUE;
private int dfs(TreeNode root, int x, int depth){
if(root==null)
return 0;
if(root.val==x)
return depth;
level=dfs(root.left, x, depth+1);
if(level<=0){
level=dfs(root.right, x, depth+1);
}
return level;
}
private TreeNode getParent(TreeNode root, int value){
if(root==null)
return null;
if(root.left!=null && root.left.val==value || root.right!=null && root.right.val==value){
return root;
}
else{

TreeNode parent=getParent(root.left, value);
if(parent==null){
parent=getParent(root.right, value);
}
return parent;
}

}
public boolean isCousins(TreeNode root, int x, int y) {
int depth1=dfs(root, x, 0);
int depth2=dfs(root, y, 0);
// System.out.println(depth1);

if(depth1==depth2){
TreeNode parent1=getParent(root, x);
TreeNode parent2=getParent(root, y);
if(parent1!=parent2){
return true;
}
}
return false;
}
}

praveenj

Your space complexity computation is incorrect. You are basically doing a depth first search with early termination. You have to consider the space the stack is going to take for your recursion. The space complexity comes out to be O(n).

klotzak

Cousins In Binary Tree LeetCode Java | LeetCode 993 | Programming Tutorials

Cousins in a binary tree | Leetcode #993

Cousins in Binary Tree II - Leetcode 2641 - Python

993. Cousins in Binary Tree - Day 18/31 Leetcode October Challenge

Cousins in Binary Tree | LeetCode 993 | Coders Camp

Cousins In Binary Tree LeetCode Java | LeetCode 993 | Programming Tutorials

Cousins in Binary Tree | cousins in binary tree | cousins in binary tree leetcode | leetcode 993

Leetcode 993 Cousins in Binary Tree

LeetCode 993 - Cousins in Binary Tree: A Microsoft Journey

LeetCode 993 | Cousins in Binary Tree | BFS | DFS | Java

993. Cousins in Binary Tree | LEETCODE | BINARY TREE

Cousins in Binary Tree - LeetCode May 7 Challenge

Cousins in Binary Tree II - Leetcode 2641 - Python

Cousins in Binary Tree | Leetcode 993 | 2 Solutions BFS + DFS | Live coding session 🔥🔥🔥

Cousins in Binary Tree | Day 7 | [May LeetCoding Challenge] [2020]

Cousins in Binary Tree (python) - Day 7/31 Leetcode May Challenge

2461. Cousins in Binary Tree II | LeetCode BiWeekly 102

Cousins in Binary Tree LeetCode | LeetCode 997 | Tree

Cousins in Binary Tree II | Leetcode 2641

Cousins in Binary Tree II | 2 Detailed Approaches | Dry Run | Leetcode 2641 | codestorywithMIK

Cousins in Binary Tree (Leetcode 993)

Cousins in binary tree leetcode python | cousins in binary tree python | leetcode coding may day 7

LeetCode | 993. Cousins in Binary Tree | Python Solution

993 : Cousins in Binary Tree | Leetcode | code + Explanations | Python

Cousins in Binary Tree || May LeetCoding Challenge || [ C++ SOLUTION ]