Cousins in a binary tree | Leetcode
HTML-код
- Опубликовано: 2 окт 2024
- This video shows a very important programming interview question based on binary tree data structure which is to find if two given nodes are cousins or not. This problem has frequently been asked in MNCs interviews both in college and off-campus and also asked for internship. I have explained the intuition for solving this problem and have taken proper examples and handled the boundary cases while explanation. I have also shown the CODE at the end of the video and the CODE LINK is given below as usual. I have also given link to some similar problems as well. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...
SIMILAR PROBLEMS:-
Binary tree maximum path sum: • Binary tree maximum pa...
Valid sequence from root to leaf in a binary tree: • Valid sequence from ro...
Construct binary search tree from preorder traversal: • Construct binary searc...
Just got this question in an interview and choked😭😭😭 Thank you for your video brother
Welcome
That problem is not easy. At least medium IMO
Leetcode marked it easy 😅
Agree!!
Medium-Hard
We can use a map to store height and parent of every root and then compare the parent and height of the given nodes accordingly.
But then space complexity increases. Map solution will be prefarable if you get queries on the same tree.
Yeh just like dsu
we can find LCA (lowest common ancestor) of the two given nodes and can be checked
It can be made simpler by getting level of both the nodes ,if level is same return true and check for parent of both the nodes if parent is same return true and then check for both conditions that if the level of both nodes is same and they are siblings then they cant be cousins.
That works too. We just need to keep 2 global variables and find both parents while traversing. If level is same then check if parents are same. Then return answer.
Good effort
making this video understandable and simple
Thanks :)
Hi, thanks so much for the explanation. I always wait for your video, can you please also make more videos on graphs?
As soon as I get time I will. In fact now I am uploading daily videos. Graph videos will only be uploaded on getting more time as it takes 8-10 times more effort in both making and editing. I hope you understand.
*I think my approach is much simpler*
_Maintaining the count of elements to be searched and finding the depth and parent in one traversal_
public class Solution {
int xDepth;
int yDepth;
TreeNode xParent;
TreeNode yParent;
int foundCount = 2;
public bool IsCousins(TreeNode root, int x, int y) {
if(root == null) return false;
IsCousinsUtil(root, x, y, null, 0);
if(foundCount == 0 && xDepth == yDepth && xParent != yParent)
return true;
else
return false;
}
public void IsCousinsUtil(TreeNode root, int x, int y, TreeNode parent, int depth) {
if(foundCount == 0)
return;
if(root == null)
return;
if(root.val == x) {
xDepth = depth;
xParent = parent;
foundCount--;
}
if(root.val == y) {
yDepth = depth;
yParent = parent;
foundCount--;
}
IsCousinsUtil(root.left, x, y, root, depth + 1);
IsCousinsUtil(root.right, x, y, root, depth + 1);
}
Yes. In the video explanation. One can easily modify the variables to make it either global or pass them in extra arguments and this can be done in just one traversal with some extra comparisons. One other simple way is to solve using levelorder traversal. I just found the 2 traversal technique to be much easier to understand :)
yes it is easy.. but what if we need to see 4 siblings then we need to add more if checks in utils to see each variable and more memory consumption of new variable , but I liked the solution ...
1) why do you have sync_with_stdio line 30
2) can solve this problem in one traversal also
1) sync studio optimizes ip op streams for cpp and so it makes its speed equal to scanf and printf.
2) yes.....a good and simple approach will be use levelorder traversal and see if you can find both elements at the same level. If only one is found at certain level then return false else if both are found at the same level then return true. I just chose recursion but you can do with anyone.
@@techdose4u 1) the input has already been read before calling the function? where can one find that the code is using cin and and not scanf?
2) We can combine the two dfs into one, and pass ans1 for x and ans2 for y, by reference, respectively to calculate the answer. this is just an optimisation.
first thought : preorder traversal and for each node check if left and right are x and y (order not imp)
It's Time And Space Complexity O( 2 n) ? Is this the Best Optimization ? If Yes , Why ? We Know There would be more Optimize if we Can Reduce it to O(Log N) ? Right ? Is that Solution exits with Help of Any Data Structure using like : HashMap, Trie, Segment Tree ? ? Please let me know if we can't get Those Solution And why ? Thank You . It's Helps a Lot
I don't think you can solve this below O(N) because the binary tree is random and has no pattern. If it is mentioned that it is a BST or tree with some special property or constraint then it can be possible but simply with this random tree, it's seemingly impossible.
what if two nodes are actually cousins but their parent names are same
Reference can never be same even though value is same 😉
Level order traversal simple solution -
public boolean isCousins(TreeNode root, int x, int y) {
Queue queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()) {
int size= queue.size();
int c=0;
for(int i=0;i1) {
return true;
}
}
return false;
}
What do you use to create videos? And editing on the screen? I am a newbie. Thinking of acquiring some skills on video making during this corona time. Could you suggest how I can start with? Which tools?
I really appreciate how precise you are about definitions of Height and Depth.
Your Leetcode walkthroughs convey the importance of using terms properly.
Well done, Sir!
I thought better we do bfs traversal and get the answer efficiently.only search level by level.
Right. Do levelorder traversal with extra space of size of queue.
@@techdose4u yea you right it will take more space.
You can do it by using Bfs right?
Hi brother , i just a beginner in java , what are the steps i have to follow to solve leetcode problems
Plz explain sir
Start solving easy questions. Try thinking for 15 mins. You cannot think then watch hint and think for 5 mins for. If that doesn't work then see the editorial or solution explained for others on discussion. You will get help on java as well. Try only easy problems for now.
Why did u update parent separately for both left and right calls?
Can you provide me the level order traversal code for this. I'm finding it hard to implement it in a code :(
Can you try implementing just level order traversal for simple binary tree using queue. You can find code on geeksforgeeks. After you do this. Solving this problem will be cakewalk. If you need help then ask here. You will get help. But first try from your side. It will be helpful.
Extra vine solution intranfuse clarity era or aged tonic
I faced problem while doing this in Java...because the parent is not passed by reference.Please Help!!
?? Read pass by reference in java or else declare it global and try.
@@techdose4u sorry but didn't quite get you...what to declare global...can you kindly mention the syntax?
Very hard , got demotivated
Can we do better. I created an pair array storing parent and depth of each node , then checked for condition. But I think there could be done something better.
I don't think we can solve this below O(N) unless given special binary tree like BST.
Is this a DFS solution using recursion?
this is my approach, but I want to make sure that if this complexity is O(max(depthx,depthy)) ?
class Solution {
public:
int depthX =-1;
int depthY = -1;
int parentX = -1;
int parentY = -1;
void getDepth(TreeNode* root,int x,int y,int c,int parent){
if(root == nullptr) return;
if(root->val == x) {
depthX = c;
parentX = parent;
if(depthY != -1) return;
}
else if (root->val == y){
depthY = c;
parentY = parent;
if(depthX != -1) return;
}
getDepth(root->left,x,y,c+1,root->val);
getDepth(root->right,x,y,c+1,root->val);
}
bool isCousins(TreeNode* root, int x, int y) {
getDepth(root,x,y,0,0);
if(depthX == depthY && parentX != parentY) return true;
return false;
}
};
It has O(N) time complexity Fatima, because you need to travel each and every node in the worst case :)
@@techdose4u yes,I just was confused thanks a lot.
Welcome :)
Your approach was simple.
But i did it using level order ------
bool isCousins(TreeNode* root, int x, int y) {
if(!root)
return 0;
TreeNode *t = new TreeNode(-1);
TreeNode *parA = NULL, *parB = NULL;
queue q;
q.push(make_pair(root, t)); //dummy node
pair p;
int level;
while(!q.empty())
{
level = q.size();
while(level--)
{
p = q.front();
q.pop();
if(p.first->val == x)
parA = p.second;
if(p.first->val == y)
parB = p.second;
if(p.first->left)
q.push(make_pair(p.first->left, p.first)); //make current node as parent then travel left
if(p.first->right)
q.push(make_pair(p.first->right, p.first));
if(parA and parB)
break;
}
if(parA and parB)
return parA != parB;
if((!parA and parB) or (parA and !parB))
return false;
}
return false;
}
Kind reminder: In your playlist of May LeetCode challenge, each video is repeating twice.
Thanks for notifying. I will correct it.
@@techdose4u You're welcome, great videos by the way! Hands down one of the best resources I could find for leetcode.
P.s. The same duplicate problem occurs towards the end of the April playlist
Okay....I will correct it soon. Please notify if you see any such problem with other playlist as well.
@@techdose4u Same issue occurs in June as well
Didn't understand "root = x or y then ......" part, can you explain it more. what is x and y at any given point of time?
We can also apply bfs if shortest path from root are equal with different predecessor then it will be cousin
Yes correct :)
what is the reason behind taking the reference of parent and not the value...plz explain!!
Sir why you have used the codes ios base and 2 more lines next to it when the data is coming as parameters of the function??
For faster io operations in c++ because cin and cout are slower than scanf and printf.
@@techdose4uok understood thanks
Why do we need line 24? I dont quite understand that since we already declared that on line 20. Thanks!
Hi I have emailed you a problem. Can you please make a video for that. Thank you :)
This approach is not completely correct as if it's a big tree then at same height many elements will be there where their parents are different but they are not cousin
do you use external mic to record your videos?
So good explanation!!!! thanks!!!!!!
Thanks :)
Hii brother, can you reveiw my code, i have taken path for both of assumed cousins, if the vector size is not equal then their height(depth) is not same then false, otherwise if true then check their parents that would probably on just next element of vector(ans[1]) if their parents are different then they are cousins and true, otherwise false bcoz they are siblings. Thanks in advance. BEGINNER HERE.
vector * rootToNodePath(TreeNode* root, int s) {
if(root == NULL) {
return NULL;
}
if(root -> val == s) {
vector *ans = new vector();
ans -> push_back(root -> val);
return ans;
}
vector *leftAns = rootToNodePath(root -> left, s);
if(leftAns != NULL) {
leftAns -> push_back(root -> val);
return leftAns;
}
vector *rightAns = rootToNodePath(root -> right, s);
if(rightAns != NULL) {
rightAns -> push_back(root -> val);
return rightAns;
}
return NULL;
}
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
vector *xPath = rootToNodePath(root, x);
vector *yPath = rootToNodePath(root, y);
if(xPath -> size() == yPath -> size()) {
return xPath -> at(1) != yPath -> at(1);
} else {
delete xPath;
delete yPath;
return false;
}
}
};
isnt this a question of BFS?
BFS=Level Order Traversal in trees
Doesn't matter if it is of BFS. If you can solve with any technique it's okay.