Bhaiya for the mark parent function there is probably no need to carry the target node seperately ig?? coz we are just marking the parent nodes for the correspnding child nodes??
To perhaps make it more clear for those still a bit confused He basically turned a Binary Tree into an Undirected Graph, this method is incredible and extremely useful.
Why cant we use DFS and create a mod distance variable which set to 0 at node and going away increment by 1 and on return decrement by 1. When it again comes to node, on return of that node it will -1. Here we can use absolute distance. Thougths?
@@someshpatel7660this won't work if the target is on the right subtree and the k distant node is on left subtree of the root. Correct me if I misunderstood
@@someshpatel7660 i used dfs to do and did it. Didn't understand what you are saying but what i did was finding descendants at k distance, then compute path from root to node marking ancestors. Now we know distance of each ancestor from node. We then move in direction away from node from these whatever steps required to get k
after doing every question of this series i get to know that main motive is not to prepare for questions in interview/coding round but to identify pattern. Must say striver your content is top notch.
Self Notes: 🍋 Mark each node to its parent to traverse upwards 🍋 We will do a BFS traversal starting from the target node 🍋 As long as we have not seen our node previously, Traverse up, left, right until reached Kth distance 🍋 when reached Kth distance, break out of BFS loop and remaining node's values in our queue is our result
with this logic , i code code k distance node downwards and upwards, really impressed with the logic , dry run took time , i did it two times though , Thanks for making such content
We can implement it using recursion as well. As on every node , there will be 3 recursion .. i.e for left , for right and for parent .. code is given below :: void makeParent(TreeNode* root,unordered_map &parent){ queue q; q.push(root); while(!q.empty()){ int n= q.size(); for(int i=0;ileft) { parent[node->left]=node; q.push(node->left); } if(node->right){ parent[node->right]=node; q.push(node->right); } } } } class Solution { public: vector distanceK(TreeNode* root, TreeNode* target, int k) { unordered_map parent; makeParent(root,parent); unordered_map visited; vector ans; solve(target,parent,visited,k,ans); return ans; } void solve(TreeNode* target,unordered_map &parent,unordered_map &visited,int k,vector &ans){ if(k==0){ ans.push_back(target->val); } visited[target]=true; if(target->left && !visited[target->left]){ solve(target->left,parent,visited,k-1,ans); } if(target->right && !visited[target->right]){ solve(target->right,parent,visited,k-1,ans); } if(parent[target]!=NULL && !visited[parent[target]]){ solve(parent[target],parent,visited,k-1,ans); } }
here is the java code with target as integer and also target as a node thank you striver bhayya for making the concept clearer public class Solution { public static List distanceK(TreeNode root, int target, int k) { Map parent = new HashMap(); markParents(root, null, parent); Queue queue = new LinkedList(); Set visited = new HashSet(); TreeNode tgt = findNode(target , root); queue.offer(tgt); visited.add(tgt); int level = 0; while (!queue.isEmpty()) { if (level == k) break; int size = queue.size(); level++; for (int i = 0; i < size; i++) { TreeNode current = queue.poll(); if (current.left != null && !visited.contains(current.left)) { queue.offer(current.left); visited.add(current.left); } if (current.right != null && !visited.contains(current.right)) { queue.offer(current.right); visited.add(current.right); } TreeNode parentNode = parent.get(current); if (parentNode != null && !visited.contains(parentNode)) { queue.offer(parentNode); visited.add(parentNode); } } } List result = new ArrayList(); while (!queue.isEmpty()) { result.add(queue.poll().val); } Collections.sort(result); return result; } public static void markParents(TreeNode root, TreeNode par, Map parent) { if (root == null) return; parent.put(root, par); markParents(root.left, root, parent); markParents(root.right, root, parent); } static TreeNode findNode(int val , TreeNode root){ if(root==null) return null; if(root.val == val) return root; TreeNode left = findNode(val , root.left); TreeNode right = findNode(val , root.right); if(left==null) return right; if(right == null) return left; return null; } }
even we can do it without storing the root to that node path , by just checking whether if a nodes leftchild contains target , then we will search for possible answers in the right subtree of current node , and if found in rightNode then w will check possible answers in left subtree , if the node is itself target than we can just see all its childrens at distance k.
What an amazing explanation. I was able to do the whole code by myself just after you did a dry run and told the logic. Thank you so much bhaiya for making trees easy for us. :)
Superb Intuition and explanation, this problem falls in the range of Hard Problem, but your technique and approach makes it super easy to understand and also code!!
i think for this method we should have used 3 pointers in a binary tree left right and parent while constructing tree and then simply traverse the tree and finding the target of the tree and then using a map i which two variable are there int for distance and node for distinct element
Basically, here we are making the undirected graph from given tree and using BFS(level order traversal of graph) to find different vertices at distance k
I have one more solution with time complexity O(2n) and space complexity O(n). 1.) Take a map which stores the pair (Node value, direction from root, left or right), eg, (4, left) 2.) in the process, store the level of the target and the direction, level=1, direction= left 3.) if the target is on left, take all the values from level+k with direction left. In our eg, from map[3], we will get 7 and 4 4.) now for ancestor, take map[k-level], so we will have map[1] and as the target value is on left, we will take the nodes with direction right from map[1]. In our example it is 1.
we also do the problem like keeping a hashtable for distance and find all the distances from the root node for the left side... and for the right side as seperate.. and then we can find the nodes with that distance.
Guys, this question was asked in Amazon interview. The twist is that we should not use a map to store the parents. Try solving it without using the map! Loved the explanation Striver!!
Key Notes: - Mark each node to its parent to traverse upwards - We will do a BFS traversal starting from the target node - As long as we have not seen our node previously, Traverse up, left, right until reached Kth distance - When reached Kth distance, break out of BFS loop and remaining node's values in our queue is our result.
Python Code to Find all Nodes a K Distance in Binary Tree: #Thanks for the Great Explanation class Solution: def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]: # Function to perform breadth-first search to find parent nodes def bfs_to_find_parents(root): parent_map = {} # Maps a node's value to its parent node if not root: return parent_map queue = deque() queue.append(root) while queue: node = queue.popleft() if node.left: queue.append(node.left) parent_map[node.left.val] = node # Store parent for left child if node.right: queue.append(node.right) parent_map[node.right.val] = node # Store parent for right child return parent_map
# Function to find nodes at distance k from the target node def find_nodes_with_distance_k(target, parent_map, k): queue = deque() queue.append(target) visited = set() visited.add(target.val) distance = 0 while distance != k: size = len(queue) while size: node = queue.popleft() # Check if parent exists and it hasn't been visited before if parent_map[node.val] and parent_map[node.val].val not in visited: queue.append(parent_map[node.val]) # Add parent to queue visited.add(parent_map[node.val].val) # Mark parent as visited # Add left child to queue if it exists and hasn't been visited if node.left and node.left.val not in visited: queue.append(node.left)# Add left child to queue visited.add(node.left.val)# Mark left child as visited # Add right child to queue if it exists and hasn't been visited if node.right and node.right.val not in visited: queue.append(node.right)# Add right child to queue visited.add(node.right.val)# Mark right child as visited size -= 1 distance += 1 return queue
# Build parent map parent_map = bfs_to_find_parents(root) parent_map[root.val] = None # Set root's parent as None
# Find nodes at distance k from target nodes_at_distance_k = find_nodes_with_distance_k(target, parent_map, k)
# Extract values of nodes at distance k result = [node.val for node in nodes_at_distance_k] return result
I encountered this problem in one of the interview I told him the approach which you have explained then he told me not to use the map to store the parents .. and then I shattered as I don't have that approach in mind. :(
In the first step you can find the nodes which are at k distance below given node using recursive traversal. Then back track to each ancestor and store distance of ancestor in variable ( say d). Back track until k-d!=0. and at each ancestor call recursive again to find node at distance k-d.
I solved it myself by another approach. Please let me know If It is a good approach or not. 1. Storing the path from root the the node in a deque using a dfs. 2. keep a count for how many elements are popped from deque 2. pop items from the front of deque and find the nodes at a dist (n - no of items popped). 3. Now to make sure that the latter popped node doesnot searches in the direction of the node popped previously we use a unordered set of popped out elements and after finding nodes at a dist for a node we put the node in the unordered set. Code: class Solution { private: bool dfs(TreeNode* root, TreeNode* target, deque &dq) { if(root == NULL) return false; if(root == target) { dq.push_back(target); return true; } bool isFound = false; isFound = dfs(root -> left, target, dq); isFound = isFound || dfs(root -> right, target, dq); if(isFound) { dq.push_back(root); return true; } return false; } void getAllNodes(TreeNode* curr, unordered_set &s, int dist, vector &res) { if(curr == NULL) return; if(s.find(curr) != s.end()) return; if(dist == 0) { res.push_back(curr -> val); return; } getAllNodes(curr -> left, s, dist - 1, res); getAllNodes(curr -> right, s, dist - 1, res); } public: vector distanceK(TreeNode* root, TreeNode* target, int k) { deque dq; unordered_set s; dfs(root, target, dq); vector res; int dist = k; while(!dq.empty()) { TreeNode* curr = dq.front(); dq.pop_front(); getAllNodes(curr, s, dist--, res); s.insert(curr); if(dist < 0) break; } return res; } };
I initiallly thought of actually converting this tree to an undirected graph and just finding K distant nodes but your observation is just best!! Can u tell me why u took visited array??
I solved it differently(return all the downward nodes at a distance k from some particular node and some simple manipulations), but i think this approach is easier to come up with if someone have studied standard graph problems
Solution :where we are given value of target Node void markparent(Node* root , unordered_map &keep_parent,int t,Node* &tn ){ if(!root) return; queue q; q.push(root); while(!q.empty()){ int n = q.size(); for(int i=0;idata==t) tn=root; //only for getting target node form given key if(root->left){ keep_parent[root->left]=root; // root k left ka parent root mark kr diya q.push(root->left); } if(root->right){ keep_parent[root->right]=root; // root k right ka parent root mark kr diya q.push(root->right); } } } }
I am thinking of anotger approach which is treating this like a directed graph. So instead of marking that whuch is the nodes parent we can just make an adj list and mark them like an undirected graph. Then we can directly do the bfs
Following is the solution using the Backtracking. In interviews, you may be asked to write without storing the parent pointers in the MAP. ===> Assume the Solution::solve() returns the vector with list of nodes at a distance of K from the target node. void findNodeAtGivenDist(TreeNode *root, vector &ans, int distance){ if(root == NULL) return;
if(distance == 0) ans.push_back(root -> val);
findNodeAtGivenDist(root -> left, ans, distance - 1); findNodeAtGivenDist(root -> right, ans, distance - 1); } int solve1(TreeNode *root, int target, int distance, vector &ans){ if(root == NULL) return 0;
if(root -> val == target){ // Find the bottom nodes from the target findNodeAtGivenDist(root, ans, distance); return 1; } int left = solve1(root -> left, target, distance, ans); int right = solve1(root -> right, target, distance, ans); if(left == distance || right == distance) { // Edge case, the current node is exactly equal to the distance ans.push_back(root -> val); } if(left > 0){ // Go to the right side and find the nodes with the given distance findNodeAtGivenDist(root -> right , ans, distance - left - 1); return left + 1; } if(right > 0){ findNodeAtGivenDist(root -> left, ans, distance - right - 1); return right + 1; } return 0; } vector Solution::solve(TreeNode* A, int B, int C) { vector ans; solve1(A, B, C, ans); return ans; }
ommmg , thanks , I was doing something completely different , I was trying to compute a list that represent that BT , and then compute the the parent and children K times until i get the result , but you're algo is a lot faster
I solved it by converting tree to graph, and take adjacency list and bfs to traverse to all nodes at a distance of k? Is it a good approach for interviews?
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List distanceK(TreeNode root, TreeNode target, int k) { Map map = new HashMap(); Set visited = new HashSet(); List list = new ArrayList(); updateParent(null, root, map); traverse(k, target, map, list, visited); return list; }
public void updateParent(TreeNode parent, TreeNode current, Map childToParent){
How do we solve this without using parent pointers or without any extra space? Is it even possible? I was asked this question in Amazon interview and the interviewer was persistent on solving without space and ultimately it led to me bombing the interview :(
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
Done brother this thing is obvious 😁
On 50 line ,i think wha pe parent_track[current]. second aana chaiye because we marked the parents like 5->3 5 ka parent 3 hai
@@ayushjain386 no it's correct 5->3 mtlb 5 ka parent 3 hai to parent_track[current] =3 hi aayega if current=5
unordered_map in c++ does take O(1) time for look up. so the time complexity in worst case will come out to O(n)
Bhaiya for the mark parent function there is probably no need to carry the target node seperately ig?? coz we are just marking the parent nodes for the correspnding child nodes??
To perhaps make it more clear for those still a bit confused
He basically turned a Binary Tree into an Undirected Graph, this method is incredible and extremely useful.
100 bat ki 1 bat
Why cant we use DFS and create a mod distance variable which set to 0 at node and going away increment by 1 and on return decrement by 1. When it again comes to node, on return of that node it will -1. Here we can use absolute distance.
Thougths?
@@someshpatel7660this won't work if the target is on the right subtree and the k distant node is on left subtree of the root. Correct me if I misunderstood
deno....
@@someshpatel7660 i used dfs to do and did it. Didn't understand what you are saying but what i did was finding descendants at k distance, then compute path from root to node marking ancestors. Now we know distance of each ancestor from node. We then move in direction away from node from these whatever steps required to get k
Thanks!
What i learned: When you have to traverse back use a map to store the parent node
these are the comments i look for they straight away go into my revision notes.
@@phatcat7924 could you please share your notes with us🥺
@@phatcat7924 Bro he is basically making a graph and doing bfs to reach all nodes at kth level.
yups
after doing every question of this series i get to know that main motive is not to prepare for questions in interview/coding round but to identify pattern. Must say striver your content is top notch.
Self Notes:
🍋 Mark each node to its parent to traverse upwards
🍋 We will do a BFS traversal starting from the target node
🍋 As long as we have not seen our node previously, Traverse up, left, right until reached Kth distance
🍋 when reached Kth distance, break out of BFS loop and remaining node's values in our queue is our result
Thank you
Your self notes help me as well 😄
Helpfull Thanks!
Wherever I go...I search for your "self notes"
Teach me your ways senpai
with this logic , i code code k distance node downwards and upwards, really impressed with the logic , dry run took time , i did it two times though , Thanks for making such content
We can implement it using recursion as well. As on every node , there will be 3 recursion .. i.e for left , for right and for parent .. code is given below ::
void makeParent(TreeNode* root,unordered_map &parent){
queue q;
q.push(root);
while(!q.empty()){
int n= q.size();
for(int i=0;ileft) {
parent[node->left]=node;
q.push(node->left);
}
if(node->right){
parent[node->right]=node;
q.push(node->right);
}
}
}
}
class Solution {
public:
vector distanceK(TreeNode* root, TreeNode* target, int k) {
unordered_map parent;
makeParent(root,parent);
unordered_map visited;
vector ans;
solve(target,parent,visited,k,ans);
return ans;
}
void solve(TreeNode* target,unordered_map &parent,unordered_map &visited,int k,vector &ans){
if(k==0){
ans.push_back(target->val);
}
visited[target]=true;
if(target->left && !visited[target->left]){
solve(target->left,parent,visited,k-1,ans);
}
if(target->right && !visited[target->right]){
solve(target->right,parent,visited,k-1,ans);
}
if(parent[target]!=NULL && !visited[parent[target]]){
solve(parent[target],parent,visited,k-1,ans);
}
}
So basically we are traversing a tree as a graph and doing BFS from the given node
yeah forming a graph and doing BFS exactly.
Its kinda funny 😂
Tree is a graph.
here is the java code with target as integer and also target as a node thank you striver bhayya for making the concept clearer public class Solution {
public static List distanceK(TreeNode root, int target, int k) {
Map parent = new HashMap();
markParents(root, null, parent);
Queue queue = new LinkedList();
Set visited = new HashSet();
TreeNode tgt = findNode(target , root);
queue.offer(tgt);
visited.add(tgt);
int level = 0;
while (!queue.isEmpty()) {
if (level == k) break;
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (current.left != null && !visited.contains(current.left)) {
queue.offer(current.left);
visited.add(current.left);
}
if (current.right != null && !visited.contains(current.right)) {
queue.offer(current.right);
visited.add(current.right);
}
TreeNode parentNode = parent.get(current);
if (parentNode != null && !visited.contains(parentNode)) {
queue.offer(parentNode);
visited.add(parentNode);
}
}
}
List result = new ArrayList();
while (!queue.isEmpty()) {
result.add(queue.poll().val);
}
Collections.sort(result);
return result;
}
public static void markParents(TreeNode root, TreeNode par, Map parent) {
if (root == null) return;
parent.put(root, par);
markParents(root.left, root, parent);
markParents(root.right, root, parent);
}
static TreeNode findNode(int val , TreeNode root){
if(root==null) return null;
if(root.val == val) return root;
TreeNode left = findNode(val , root.left);
TreeNode right = findNode(val , root.right);
if(left==null) return right;
if(right == null) return left;
return null;
}
}
crux : converted tree into an undirected graph and applied a dfs / bfs .
you can also do it in O(H) space by stroring root to target node path and then calling the k-down function on them.
even we can do it without storing the root to that node path , by just checking whether if a nodes leftchild contains target , then we will search for possible answers in the right subtree of current node , and if found in rightNode then w will check possible answers in left subtree , if the node is itself target than we can just see all its childrens at distance k.
@@nikhilmeena8585nope it fail in some of the test cases
What an amazing explanation. I was able to do the whole code by myself just after you did a dry run and told the logic. Thank you so much bhaiya for making trees easy for us. :)
Why everything becomes soo easy when striver teaches it ? Mann you are magical 💖
ya
Superb Intuition and explanation, this problem falls in the range of Hard Problem, but your technique and approach makes it super easy to understand and also code!!
I basically learned if we want to go backward in a tree we need to use a map to store the parent node.........Incredible !
i think for this method we should have used 3 pointers in a binary tree left right and parent while constructing tree and then simply traverse the tree and finding the target of the tree and then using a map i which two variable are there int for distance and node for distinct element
Basically, here we are making the undirected graph from given tree and using BFS(level order traversal of graph) to find different vertices at distance k
yes
yeah more like creating a adjaceny list and then doing BFS from target node
starting mae toh ache samaj nhi aa rha tha .
but jaise hi code walk through kra ... sab samaj aa gaya ache se.
Thanks!!
For me this is the most awaited video..
Love you striver 😍
here, the problem in leetcode has constraints given that 0
I have one more solution with time complexity O(2n) and space complexity O(n).
1.) Take a map which stores the pair (Node value, direction from root, left or right), eg, (4, left)
2.) in the process, store the level of the target and the direction, level=1, direction= left
3.) if the target is on left, take all the values from level+k with direction left. In our eg, from map[3], we will get 7 and 4
4.) now for ancestor, take map[k-level], so we will have map[1] and as the target value is on left, we will take the nodes with direction right from map[1]. In our example it is 1.
if we have to traverse a tree upward then we have to make parent map which store the parent of every node , Nice explanation.
There is no need of passing target to makr parent function.
we also do the problem like keeping a hashtable for distance and find all the distances from the root node for the left side... and for the right side as seperate.. and then we can find the nodes with that distance.
I just coded the solution with the explanation . THANK YOU STRIVER BHAI
to mark visited nodes we can use set instead of map.
The easiest explanation for this problem so far on youtube.
Guys, this question was asked in Amazon interview. The twist is that we should not use a map to store the parents. Try solving it without using the map! Loved the explanation Striver!!
Another way is to record ancestors and then traverse away from node from these ancestors. whatever distance needed:
void descendents(TreeNode* root, int k,vector&res)
{
if(root==NULL || kval);
descendents(root->left,k-1,res);
descendents(root->right,k-1,res);
}
void ancestorcompute(TreeNode* root,TreeNode*target, vector&anc,bool&flag)
{
if(root==NULL||flag)
return;
anc.push_back(root);
if(root==target)
{
flag=true;
return;
}
ancestorcompute(root->left,target,anc,flag);
if(!flag)
ancestorcompute(root->right,target,anc,flag);
else
return;
if(!flag)
anc.pop_back();
}
vector distanceK(TreeNode* root, TreeNode* target, int k) {
if(root==NULL)
return {};
vectorres;
//first compute in descendants
descendents(target,k,res);
//find ancestors of node
vectoranc;
bool flag=false;
ancestorcompute(root,target,anc,flag);
int sz=anc.size();
for(int j=sz-2;j>=0;j--)
{
if(sz-1-j==k){
res.push_back(anc[j]->val);
break;
}
else if(anc[j]->left==anc[j+1])
{
//go in right
descendents(anc[j]->right,k-1-(sz-1-j),res);
}
else
{
descendents(anc[j]->left,k-1-(sz-1-j),res);
}
}
return res;
}
Sometimes you make the easy questions very complex.
Key Notes:
- Mark each node to its parent to traverse upwards
- We will do a BFS traversal starting from the target node
- As long as we have not seen our node previously, Traverse up, left, right until reached Kth distance
- When reached Kth distance, break out of BFS loop and remaining node's values in our queue is our result.
Python Code to Find all Nodes a K Distance in Binary Tree:
#Thanks for the Great Explanation
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
# Function to perform breadth-first search to find parent nodes
def bfs_to_find_parents(root):
parent_map = {} # Maps a node's value to its parent node
if not root:
return parent_map
queue = deque()
queue.append(root)
while queue:
node = queue.popleft()
if node.left:
queue.append(node.left)
parent_map[node.left.val] = node # Store parent for left child
if node.right:
queue.append(node.right)
parent_map[node.right.val] = node # Store parent for right child
return parent_map
# Function to find nodes at distance k from the target node
def find_nodes_with_distance_k(target, parent_map, k):
queue = deque()
queue.append(target)
visited = set()
visited.add(target.val)
distance = 0
while distance != k:
size = len(queue)
while size:
node = queue.popleft()
# Check if parent exists and it hasn't been visited before
if parent_map[node.val] and parent_map[node.val].val not in visited:
queue.append(parent_map[node.val]) # Add parent to queue
visited.add(parent_map[node.val].val) # Mark parent as visited
# Add left child to queue if it exists and hasn't been visited
if node.left and node.left.val not in visited:
queue.append(node.left)# Add left child to queue
visited.add(node.left.val)# Mark left child as visited
# Add right child to queue if it exists and hasn't been visited
if node.right and node.right.val not in visited:
queue.append(node.right)# Add right child to queue
visited.add(node.right.val)# Mark right child as visited
size -= 1
distance += 1
return queue
# Build parent map
parent_map = bfs_to_find_parents(root)
parent_map[root.val] = None # Set root's parent as None
# Find nodes at distance k from target
nodes_at_distance_k = find_nodes_with_distance_k(target, parent_map, k)
# Extract values of nodes at distance k
result = [node.val for node in nodes_at_distance_k]
return result
I encountered this problem in one of the interview I told him the approach which you have explained then he told me not to use the map to store the parents .. and then I shattered as I don't have that approach in mind. :(
U can store root to target node path
In the first step you can find the nodes which are at k distance below given node using recursive traversal. Then back track to each ancestor and store distance of ancestor in variable ( say d). Back track until k-d!=0. and at each ancestor call recursive again to find node at distance k-d.
what about pair, you can use that also!Maybe!
Actually there's no need of "target" parameter in markParent function as it isn't used anywhere!
I solved it myself by another approach. Please let me know If It is a good approach or not.
1. Storing the path from root the the node in a deque using a dfs.
2. keep a count for how many elements are popped from deque
2. pop items from the front of deque and find the nodes at a dist (n - no of items popped).
3. Now to make sure that the latter popped node doesnot searches in the direction of the node popped previously we use a unordered set of popped out elements and after finding nodes at a dist for a node we put the node in the unordered set.
Code: class Solution {
private:
bool dfs(TreeNode* root, TreeNode* target, deque &dq) {
if(root == NULL) return false;
if(root == target) {
dq.push_back(target);
return true;
}
bool isFound = false;
isFound = dfs(root -> left, target, dq);
isFound = isFound || dfs(root -> right, target, dq);
if(isFound) {
dq.push_back(root);
return true;
}
return false;
}
void getAllNodes(TreeNode* curr, unordered_set &s, int dist, vector &res) {
if(curr == NULL) return;
if(s.find(curr) != s.end()) return;
if(dist == 0) {
res.push_back(curr -> val);
return;
}
getAllNodes(curr -> left, s, dist - 1, res);
getAllNodes(curr -> right, s, dist - 1, res);
}
public:
vector distanceK(TreeNode* root, TreeNode* target, int k) {
deque dq;
unordered_set s;
dfs(root, target, dq);
vector res;
int dist = k;
while(!dq.empty()) {
TreeNode* curr = dq.front();
dq.pop_front();
getAllNodes(curr, s, dist--, res);
s.insert(curr);
if(dist < 0) break;
}
return res;
}
};
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I initiallly thought of actually converting this tree to an undirected graph and just finding K distant nodes but your observation is just best!!
Can u tell me why u took visited array??
So that I dont go back to them..
@@takeUforward sir u can visit back only parent nodes right? And that can be maintained using a variable?
@@Yash-uk8ib We can also revisit the target node from parent node(for eg 3 to 5)
Ek TVF and dusra TUF bas ye dono hee rocking hai abhi tou.
accha
I solved it differently(return all the downward nodes at a distance k from some particular node and some simple manipulations), but i think this approach is easier to come up with if someone have studied standard graph problems
I leanned a new approach thanks to u sir
What is the need of passing target node as argument of the function markparen()
simple to understand code , thank you
Thank you so much Striver !.
GOD Level Explanation 🫡🫡
Perfect and most efficient explanation.. But small optimisation would be using hash set instead of Hashmap for visited.
Thankyou so much for great explanation Striver
for getting nodes at distance k
visited map and array is not required
only previous node is enough so that it doesn't call back
(visited not required because this is not cyclic graph)
for getting nodes at distance k CODE
void dfsNodesAtDistanceK(TreeNode *node, TreeNode *pre, int k, unordered_map &parentMap, vector &ans) {
if (k==0) {
ans.push_back(node->val);
return;
}
if (node->left && node->left!=pre) {
dfsNodesAtDistanceK(node->left, node, k-1, parentMap, ans);
}
if (node->right && node->right!=pre) {
dfsNodesAtDistanceK(node->right, node, k-1, parentMap, ans);
}
TreeNode *parent = parentMap[node];
if (parent!=NULL && parent!=pre) {
dfsNodesAtDistanceK(parent, node, k-1, parentMap, ans);
}
return;
}
FULL CODE
class Solution {
private:
void markParents(TreeNode *root, unordered_map &parentMap) {
queue nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
TreeNode *node = nodeQueue.front();
nodeQueue.pop();
if (node->left) {
parentMap[node->left] = node;
nodeQueue.push(node->left);
}
if (node->right) {
parentMap[node->right] = node;
nodeQueue.push(node->right);
}
}
return;
}
void dfsNodesAtDistanceK(TreeNode *node, TreeNode *pre, int k, unordered_map &parentMap, vector &ans) {
if (k==0) {
ans.push_back(node->val);
return;
}
if (node->left && node->left!=pre) {
dfsNodesAtDistanceK(node->left, node, k-1, parentMap, ans);
}
if (node->right && node->right!=pre) {
dfsNodesAtDistanceK(node->right, node, k-1, parentMap, ans);
}
TreeNode *parent = parentMap[node];
if (parent!=NULL && parent!=pre) {
dfsNodesAtDistanceK(parent, node, k-1, parentMap, ans);
}
return;
}
public:
vector distanceK(TreeNode* root, TreeNode* target, int k) {
unordered_map parentMap;
markParents(root, parentMap);
vector ans;
dfsNodesAtDistanceK(target, NULL, k, parentMap, ans);
return ans;
}
};
863. All Nodes Distance K in Binary Tree
Solution :where we are given value of target Node
void markparent(Node* root , unordered_map &keep_parent,int t,Node* &tn ){
if(!root) return;
queue q;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i=0;idata==t) tn=root; //only for getting target node form given key
if(root->left){
keep_parent[root->left]=root; // root k left ka parent root mark kr diya
q.push(root->left);
}
if(root->right){
keep_parent[root->right]=root; // root k right ka parent root mark kr diya
q.push(root->right);
}
}
}
}
vector KDistanceNodes(Node* root , int target , int k){
unordered_map Keep_parent ;
Node* targetN =NULL;
markparent(root,Keep_parent,target,targetN); // sare parent aa gye
unordered_map visted;
queue q;
q.push(targetN);
visted[targetN] = true;
int curr_dist=0;
while(!q.empty()){
int size = q.size();
if(curr_dist++ == k) break;
for(int i=0;ileft && !visted[curr->left]) {
q.push(curr->left);
visted[curr->left]=true;
}
if(curr->right && !visted[curr->right]) {
q.push(curr->right);
visted[curr->right]=true;
}
if(Keep_parent[curr] && !visted[Keep_parent[curr]]) {
q.push(Keep_parent[curr]);
visted[Keep_parent[curr]]=true;
}
}
}
vector ans;
while(!q.empty()){
Node* temp = q.front();
q.pop();
ans.push_back(temp->data);
}
sort(ans.begin(),ans.end());
return ans;
}
What a mind blowing solution!!
I am thinking of anotger approach which is treating this like a directed graph. So instead of marking that whuch is the nodes parent we can just make an adj list and mark them like an undirected graph. Then we can directly do the bfs
Solution without using any extra space for storing the parent:
class Solution {
public:
vector ans;
void down(TreeNode* target,int k){
if(!target)return;
if(k==0){
ans.push_back(target->val);
return;
}
down(target->left,k-1);
down(target->right,k-1);
}
bool up(TreeNode* root,TreeNode* target,int &k){
if(!root)return false;
if(root==target)return true;
if(up(root->left,target,k)){
k--;
if(k==0)ans.push_back(root->val);
down(root->right,k-1);
return true;
}
if(up(root->right,target,k)){
k--;
if(k==0)ans.push_back(root->val);
down(root->left,k-1);
return true;
}
return false;
}
vector distanceK(TreeNode* root, TreeNode* target, int k) {
down(target,k);
up(root,target,k);
return ans;
}
};
Thank you for the best possible solution. Hats off to your efforts
Following is the solution using the Backtracking. In interviews, you may be asked to write without storing the parent pointers in the MAP.
===> Assume the Solution::solve() returns the vector with list of nodes at a distance of K from the target node.
void findNodeAtGivenDist(TreeNode *root, vector &ans, int distance){
if(root == NULL)
return;
if(distance == 0)
ans.push_back(root -> val);
findNodeAtGivenDist(root -> left, ans, distance - 1);
findNodeAtGivenDist(root -> right, ans, distance - 1);
}
int solve1(TreeNode *root, int target, int distance, vector &ans){
if(root == NULL)
return 0;
if(root -> val == target){
// Find the bottom nodes from the target
findNodeAtGivenDist(root, ans, distance);
return 1;
}
int left = solve1(root -> left, target, distance, ans);
int right = solve1(root -> right, target, distance, ans);
if(left == distance || right == distance)
{
// Edge case, the current node is exactly equal to the distance
ans.push_back(root -> val);
}
if(left > 0){
// Go to the right side and find the nodes with the given distance
findNodeAtGivenDist(root -> right , ans, distance - left - 1);
return left + 1;
}
if(right > 0){
findNodeAtGivenDist(root -> left, ans, distance - right - 1);
return right + 1;
}
return 0;
}
vector Solution::solve(TreeNode* A, int B, int C) {
vector ans;
solve1(A, B, C, ans);
return ans;
}
Basically convert tree into a undirected graph start from target and do k iteration of BFS ?
ommmg , thanks , I was doing something completely different , I was trying to compute a list that represent that BT , and then compute the the parent and children K times until i get the result , but you're algo is a lot faster
You are magic striver and you create magic
Thanks for such a great explanation striver...
This was a very good question , learnt multiple new approaches from this one ..
Should this(or a similar) question be asked in an interview? Because it took me almost 1 hour to just code!
Yes definitely,You have to work on your speed.
Super explanation
Nice and easy explaination. !
Ill do this again , accha problem hai revision lagega
thenks striver
Why we take the target arguement in markparents function?
did you find answer to this?
Understood! Such a fantastic explanation as always, thank you very much!!
Please do a smooth transition from black iPad to white Code screen...I've become blind because of the quick transition 😥
Love you bhai love you, You are amazing, amazing explaination.
the 2nd toughest quetion so far of this series
why have we taken target as one of the argument in markParents function?
Awesome explanation 💫💫!!!
Understood .....
please make videos on finding time complexity of finding complex questions
Comes with practice, don't think on that too much :)
I solved it by converting tree to graph, and take adjacency list and bfs to traverse to all nodes at a distance of k? Is it a good approach for interviews?
bhai kya gaaannnddddd faaaaadddd playlist hai maza aagaya
why are you passing the target node int mark parent function?
Thank you for the explanation, really helpful
we can avoid second loop using one more queue
you are amazing tutor #takeuForward bro
Amazing explanation😇
I have one doubt -this above apprach will get fail when tree will not be a binary tree right??
Very well explained bhaiya! understood🔥
So purpose was to convet tree into undirected graph
This can be easily solved using
1) root to node path
2) print all nodes k level down
why are we taking target as parameter in markparents function
GOD level explanation 🫡🫡
Do I need to go with a brute-better-optimal solution for this approach in the interview if asked??
Yes, that's the way u need to go
why time complexity is o(N) why not o(N)square perhaps we are using two nested loops please tell ..i am a beginner
very well explained thankyou sir
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List distanceK(TreeNode root, TreeNode target, int k) {
Map map = new HashMap();
Set visited = new HashSet();
List list = new ArrayList();
updateParent(null, root, map);
traverse(k, target, map, list, visited);
return list;
}
public void updateParent(TreeNode parent, TreeNode current, Map childToParent){
if(current == null)
return;
childToParent.put(current, parent);
updateParent(current, current.left, childToParent);
updateParent(current, current.right, childToParent);
}
public void traverse(int distance, TreeNode node, Map childToParent,
List list, Set visited){
if(node == null)
return;
if(visited.contains(node))
return;
visited.add(node);
if(distance == 0){
list.add(node.val);
return;
}
traverse(distance-1, node.left, childToParent, list, visited);
traverse(distance-1, node.right, childToParent, list, visited);
traverse(distance-1, childToParent.get(node), childToParent, list, visited);
}
}
Good explanation bro. Understood properly. Thankyou :)
How do we solve this without using parent pointers or without any extra space? Is it even possible? I was asked this question in Amazon interview and the interviewer was persistent on solving without space and ultimately it led to me bombing the interview :(
we could use Set to keep track of visited nodes.
public List distanceK(TreeNode root, TreeNode target, int k) {
Map parentMap = markParentNodes(root);
Set visited = new HashSet();
Deque queue = new LinkedList();
visited.add(target);
queue.offer(target);
int currentLevel = 0 , size = 0;
while (!queue.isEmpty()) {
if (currentLevel == k) break;
currentLevel++;
size = queue.size();
for (int i = 0; i< size; i++) {
TreeNode node = queue.poll();
if (node.left != null && !visited.contains(node.left)) {
queue.offer(node.left);
visited.add(node.left);
}
if (node.right != null && !visited.contains(node.right)) {
queue.offer(node.right);
visited.add(node.right);
}
TreeNode parent = parentMap.get(node);
if (parent != null && !visited.contains(parent)) {
queue.offer(parent);
visited.add(parent);
}
}
}
return queue.stream().map(node -> node.val).toList();
}
public Map markParentNodes(TreeNode root) {
Map parentMap = new HashMap();
// store
Deque queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
parentMap.put(node.left, node);
queue.offer(node.left);
}
if (node.right != null) {
parentMap.put(node.right, node);
queue.offer(node.right);
}
}
return parentMap;
}
Nice explanation☺
Store parents and do normal bfs using visited array
Understood, Great explanation! 🤩
If it was print all from lead node. What changes has to be done?
just one word - amazing
What happens when we get two nodes of same value?? Will unordered map work at that time??
class Solution {
private:
void mapping(TreeNode* root, map&nodetoparent){
if(root==NULL){
return;
}
nodetoparent[root]=NULL;
queueq;
q.push(root);
while(!q.empty()){
TreeNode* front=q.front();
q.pop();
if(front->left){
nodetoparent[front->left]=front;
q.push(front->left);
}
if(front->right){
nodetoparent[front->right]=front;
q.push(front->right);
}
}
}
public:
vector distanceK(TreeNode* root, TreeNode* target, int k) {
mapnodetoparent;
mapping(root, nodetoparent);
queueq;
q.push(target);
mapvisited;
visited[target]=true;
int d=0;
while(d!=k){
int size=q.size();
for(int i=0; ileft && visited[front->left]==false){
visited[front->left]=true;
q.push(front->left);
}
if(front->right && visited[front->right]==false){
visited[front->right]=true;
q.push(front->right);
}
if(nodetoparent[front] && visited[nodetoparent[front]]==false){
visited[nodetoparent[front]]=true;
q.push(nodetoparent[front]);
}
}
d++;
}
vectorres;
while(!q.empty()){
TreeNode* front = q.front();
res.push_back(front->val);
q.pop();
}
return res;
}
🔥couldn’t have been better!
amazing explanation. 😃😃😃
Amazing explanation! Thankyou so much :)