solved using python by your approach # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]: res = [] parent = {} visited = set() def preorder(node): if node is None: return if node.left: parent[node.left] = node preorder(node.left) if node.right: parent[node.right] = node preorder(node.right) preorder(root) q = collections.deque() q.append(target) while q: if not k: break for _ in range(len(q)): node = q.popleft() visited.add(node.val) if node.left and node.left.val not in visited: q.append(node.left) if node.right and node.right.val not in visited: q.append(node.right) if node in parent and parent[node].val not in visited: q.append(parent[node]) k -= 1 while q: res.append(q.popleft().val) return res
I woke up in the morning attempted this ..i was so out of my mind ki mei queue soch ke stack ke hisab se pop kar raha hun dry run mei 😂😂 then finally samjha ki kitna bada blunder kar raha tha ... Thanks MIK ❤
you have very unique skill to explain very good problems in a very understandable way only one request sir please continue these series of solving dialy problems sir finally a big thanks to you sir whenever i fell demotivated in DSA after seeing ur solutions again i am pumped up to solve questions sir
Indeed the interviewer will ask for better one. And that’s why I made a separate video on approach-1 Definitely I am gonna make Approach-2 video as well 😇❤️
@floatingpoint7629 It’s not a bad approach. However, it can be solved without using map and parent pointer. So, in case interviewer asks to solve without using parent pointers.
Hey I have been following ur videos to help me solve my daily leetcode problems, and the way u teach is impressive and it motivates me to do atleast one question everyday. Thanks fror the content you put out, hope you keep doing this and would love to get to interact with you , as a mentor or a guide coz i am pretty confused and unguided all the time. Once again thank you, if you are looking at this comment please do reply, would love to get to message you irl. Thank you
It would be better to have a hashmap of TreeNodes rather than int, suppose you have repeated numbers at kth distance from target, then it would print it only once.
I was waiting for your video since morning so that i can get more approaches ,this hash-map approach is everywhere but what if i have to solve this question without hash-map without using parent-child relationship and also not converting it into graph.so can you solve this with another approach. I have doubt in one code can you make me understand how that code is running class Solution { public: vector distanceK(TreeNode* root, TreeNode* target, int k) { vector res; dfs(root, target, k, res); return res; }
private: int dfs(TreeNode* node, TreeNode* target, int k, vector& res) { if (!node) { return -1; } if (node == target) { subtreeAdd(node, 0, k, res); return 0; } int left = dfs(node->left, target, k, res); int right = dfs(node->right, target, k, res); if (left != -1) { if (left + 1 == k) { res.push_back(node->val); } subtreeAdd(node->right, left + 2, k, res); return left + 1; } if (right != -1) { if (right + 1 == k) { res.push_back(node->val); } subtreeAdd(node->left, right + 2, k, res); return right + 1; } return -1; }
void subtreeAdd(TreeNode* node, int dist, int k, vector& res) { if (!node) { return; } if (dist == k) { res.push_back(node->val); } subtreeAdd(node->left, dist + 1, k, res); subtreeAdd(node->right, dist + 1, k, res); } };
crystal clear explanation.Thank you bhaiya
Thanks a lot Bishal ❤️
Parent pointer wala intuition 🔥
you are simple awesome MIK
solved using python by your approach
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
res = []
parent = {}
visited = set()
def preorder(node):
if node is None:
return
if node.left:
parent[node.left] = node
preorder(node.left)
if node.right:
parent[node.right] = node
preorder(node.right)
preorder(root)
q = collections.deque()
q.append(target)
while q:
if not k:
break
for _ in range(len(q)):
node = q.popleft()
visited.add(node.val)
if node.left and node.left.val not in visited:
q.append(node.left)
if node.right and node.right.val not in visited:
q.append(node.right)
if node in parent and parent[node].val not in visited:
q.append(parent[node])
k -= 1
while q:
res.append(q.popleft().val)
return res
Nice explanation, keep going
Thank you 🙂❤️
This was asked to me in Amazon interview
Wow 😯
I woke up in the morning attempted this ..i was so out of my mind ki mei queue soch ke stack ke hisab se pop kar raha hun dry run mei 😂😂 then finally samjha ki kitna bada blunder kar raha tha ...
Thanks MIK ❤
🤓🤓
Thank you for watching ❤️❤️
Thank you so much ❤
You're welcome 😊
Beautiful explanation 😊
So intuitive !!! 💡
Thanks Sir 🙏
Thank you for watching ❤️🙏
bhiya pls contest ki bhi vedio bnao
Sure. I will be back to India next week.
Let me try to put more of contests
Good explanation with dryrun
Thanks a lot 🙏😇
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map parent;
void inorder(TreeNode* root){
if(root==NULL){
return ;
}
if(root->left){
parent[root->left]=root;
}
inorder(root->left);
if(root->right){
parent[root->right]=root;
}
inorder(root->right);
}
void bfs(TreeNode* target, int k,vector &res ){
queue q;
q.push(target);
unordered_set visited;
visited.insert(target->val);
while(!q.empty()){
int size = q.size();
if(k==0) break;
while(size--){
TreeNode* curr = q.front();
q.pop();
if(curr->left && !visited.count(curr->left->val)){
q.push(curr->left);
visited.insert(curr->left->val);
}
if(curr->right && !visited.count(curr->right->val)){
q.push(curr->right);
visited.insert(curr->right->val);
}
if(parent.count(curr) && !visited.count(parent[curr]->val)){
q.push(parent[curr]);
visited.insert(parent[curr]->val);
}
}
k--;
}
while(!q.empty()){
TreeNode* temp = q.front();
q.pop();
res.push_back(temp->val);
}
}
vector distanceK(TreeNode* root, TreeNode* target, int k) {
vector res;
inorder(root);
bfs(target,k, res);
return res;
}
};
Great Explanation 👌🏻
Thank you so much Anup ❤️❤️
Thanks a lot
you have very unique skill to explain very good problems in a very understandable way only one request sir please continue these series of solving dialy problems sir finally a big thanks to you sir whenever i fell demotivated in DSA after seeing ur solutions again i am pumped up to solve questions sir
Thank you so much 🙏😇❤️
The way you explained this is so simple and intuitive. Thanks a lot
Best explanation
You have the skill to make things look like a CAKE WALK ❤
I still am so glad that I found this channel
@codestorywithMIK Can you upload Video on the other approach to solve this question
Awesome explanation 👍👍👍
Glad you liked it 👍🏻🙏
inorder traversal ( left root node)
Please make a video without using parent pointer
thanks for the explanation. i was able to solve this one by self 😄
Wowieee. Awesome 😍😇🙏
Dp concept and qns series ko please continue kardo 🥺🥺
Yes yes.Coming today/tomorrow ❤️❤️🙏🙏
more intutive is Postorder
Thank you for sharing 😇
asusual no one can beat ypu in explaining the concept ans dsa question
Sir my brute approach was to convert the tree into adj list form since each node->vak is unique . Is it not good for interview ?
That’s absolutely an acceptable approach.
Also leetcode has put this in their official solution
I think bhaiya interviewer will not be happy with this approach 😢.Please make video on second approach soon.
Indeed the interviewer will ask for better one. And that’s why I made a separate video on approach-1
Definitely I am gonna make Approach-2 video as well 😇❤️
whats wrong with this approach. this is the official approach chosen by leetcode itself
@floatingpoint7629 It’s not a bad approach. However, it can be solved without using map and parent pointer. So, in case interviewer asks to solve without using parent pointers.
@@codestorywithMIK got it. looking forward to that solution 😀
I'm waiting for that 😁
Made it a cake walk ❤❤
Hey I have been following ur videos to help me solve my daily leetcode problems, and the way u teach is impressive and it motivates me to do atleast one question everyday. Thanks fror the content you put out, hope you keep doing this and would love to get to interact with you , as a mentor or a guide coz i am pretty confused and unguided all the time. Once again thank you, if you are looking at this comment please do reply, would love to get to message you irl. Thank you
Thanks a lot 🙏😇❤️
You can connect on LinkedIn
❤
bhai please approach 2 jaldi le lao please request he
It would be better to have a hashmap of TreeNodes rather than int, suppose you have repeated numbers at kth distance from target, then it would print it only once.
Can we store the parent mapping using level order traversal ??
Yes definitely
Ohkk , thnx
bhai itna dimag kaisai lagaya first attempt mai toh mere sai kabhi bhhi nahi hota
Can anyone share the bfs video where he talks about the bfs logic when to use which bfs techniques
I was waiting for your video since morning so that i can get more approaches ,this hash-map approach is everywhere but what if i have to solve this question without hash-map without using parent-child relationship and also not converting it into graph.so can you solve this with another approach. I have doubt in one code can you make me understand how that code is running class Solution {
public:
vector distanceK(TreeNode* root, TreeNode* target, int k) {
vector res;
dfs(root, target, k, res);
return res;
}
private:
int dfs(TreeNode* node, TreeNode* target, int k, vector& res) {
if (!node) {
return -1;
}
if (node == target) {
subtreeAdd(node, 0, k, res);
return 0;
}
int left = dfs(node->left, target, k, res);
int right = dfs(node->right, target, k, res);
if (left != -1) {
if (left + 1 == k) {
res.push_back(node->val);
}
subtreeAdd(node->right, left + 2, k, res);
return left + 1;
}
if (right != -1) {
if (right + 1 == k) {
res.push_back(node->val);
}
subtreeAdd(node->left, right + 2, k, res);
return right + 1;
}
return -1;
}
void subtreeAdd(TreeNode* node, int dist, int k, vector& res) {
if (!node) {
return;
}
if (dist == k) {
res.push_back(node->val);
}
subtreeAdd(node->left, dist + 1, k, res);
subtreeAdd(node->right, dist + 1, k, res);
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void inorder(TreeNode *root , vector adj[])
{
if(not root)
return;
if(root -> left)
{
adj[root -> left -> val].push_back(root -> val);
adj[root -> val].push_back(root -> left -> val);
}
inorder(root -> left , adj);
if(root -> right)
{
adj[root -> right -> val].push_back(root -> val);
adj[root -> val].push_back(root -> right -> val);
}
inorder(root -> right , adj);
}
vector distanceK(TreeNode* root, TreeNode* target, int k) {
vector adj[501];
inorder(root , adj);
vector visited(501 , false);
for(int i = 0 ; i < 3 ; i++)
{
cout
Can u please create Recursion playlist?
bhaiya dp playlist kaafi time sai update nhi hui plz atleast 1 week mai 3 video daal diya kaaro dp ki 🥲🥲
Sure thing. Will upload this week ❤️❤️❤️
Where is the approach 2
Wow itna easy tha kya ye 😥
Thnk u for the soln. Main to pta nhi kya tatti approach laga rha tha level order traversal ke sath 🥲😞