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.
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); } }
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.
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
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.
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; } }
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.
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!!
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. :)
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
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
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
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 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 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
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 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 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?
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.
