Bro you literally just blew my mind, holy hell. I have never seen a solution like this before, nor have ever thought to convert a binary tree into an undirected graph, this is literally amazing. You need more subs and likes cause you deserve it
Happy you enjoyed the video! Yea converting to a graph is a super cool approach to some of these questions, especially if you aren’t allowed to modify the original tree or don’t want to use a DFS. Let me know if there’s any other problems you’d like me to make videos for and I’ll add them to my queue.
Your solution is actually O(N*N) Worst case scenario we have to go n-1 steps from start to target. Since you used a string to represent your path, which is immutable, the path must be reprocessed each time. Thus, at the n-1 step, when you add direction to cur_path you iterate through cur_path one by one to form the new string (string is immutable). Since this is the case at each step it’s O(n^2). You can easily fix this by using a list instead of a string, which you can append to in constant time. Still a helpful video!
You're (99%) right in that I should have used a string builder here because it's actually O(N) in the total runtime. There's actually a very lesser known implementation in Python built into the CPython core library that if you do += with a string, it will actually concatenate in constant time. Though I forgot it needs to be += and just used + here to concat the strings. You can read about this here: doc.pypy.org/en/latest/cpython_differences.html#performance-differences Though yea I should have been more careful and most people (including interviewers) will probably not known or accept that 😂
@@crackfaang thank you so much! Just used this in my FAANG interview, they didn’t understand/know at first but they were definitely impressed I knew this. I wouldn’t have known without you!
@@jackkelley5409 Haha amazing! Yea it was a pretty clever solution I must admit. I really like these problems where you take some input and make a graph out of it so you can traverse it. Hope you passed your interview!
Mate, big respect for such profound explanation - it definitely made me less scared of such examples!:) Keep up the good work, you are making community much better!
Thanks for this tutorial. This a good solution indeed. While there are other solutions for this problem that works with the original tree, transforming it first to undirected graph and then use a breadth-first search on the generated graph is a nice and neat solution and it does will help demonstrate the knowledge of trees and graphs for the student. It is also much cleaner, with code in two parts: creating the graph representation of the tree and then doing a bfs on the generated graph.
This causes a memory limit exceeded in C++. Instead you could find the lowest common ancestor (LCA) and then just append the correct number of ‘U’s to the front of the path to destValue from the LCA.
Could be, I can only guarantee the solutions are accepted in Python. Though even with the official Leetcode solutions, due to the way they use dynamic cutoffs for the Time/Memory limits, even they can be TLE/MLE. As long as you know the algorithm is correct and the time/space complexity is correct, doesn't matter if the judge accepts it or not. Sometimes Leetcode's judge just doesn't accept for strange reasons
There is another solution where you search from root to start node, then root to des node, and figure out how to combine those two paths to get the solution. My first approach was to do the bfs but it felt bad because we would end up storing so many different path strings
nice video, i have question about the space complexity ... why its not o(N + E) where N is number of nodes and E is the edges ? cas this graph is like adjacency list ? or i am getting it wrong ?
This is the iterative solution. Typically they will only ask you to rewrite a solution that was recursive if it's just too simple using recursion. A common example is an inorder traversal of a binary tree using DFS. With recursion it's a one liner in Python. Iteratively it's much harder to implement and actually tests whether you understand how an inorder traversal works and how to use the stack correctly to do it.
Breadth first search through an undirected graph will always give the shortest path. It’s just a characteristic of breadth first search. Same how an I order traversal through a binary search tree gives all the nodes in sorted order
Hmm that’s fine, the leetcode judge does that sometimes when people submit enough. The solution is still valid though, there’s some questions where even the leetcode official solutions TLE
Sorry to hear you’re having trouble with the solution. Unfortunately I can only provide solutions which work in Python. And I personally would not recommend doing these questions in Swift. Most interviewers are unfamiliar with this language and unless you get someone who does iOS development, it might cost you the interview
You don't need to create a Tree Node class or the Pair class. Though my solution is guaranteed to work in Python only. I don't know if the Leetcode judge will accept the same solution in a different language as there are different time and memory cutoffs based on the language
Bro you literally just blew my mind, holy hell. I have never seen a solution like this before, nor have ever thought to convert a binary tree into an undirected graph, this is literally amazing.
You need more subs and likes cause you deserve it
Happy you enjoyed the video! Yea converting to a graph is a super cool approach to some of these questions, especially if you aren’t allowed to modify the original tree or don’t want to use a DFS.
Let me know if there’s any other problems you’d like me to make videos for and I’ll add them to my queue.
@@crackfaang Text Justification on Leetcode, one of Googles most asked questions, its insane
@@crackfaang it would be great if you could add 1284 to your queue. I assume your queue is not a priority queue :D
Your solution is actually O(N*N)
Worst case scenario we have to go n-1 steps from start to target.
Since you used a string to represent your path, which is immutable, the path must be reprocessed each time.
Thus, at the n-1 step, when you add direction to cur_path you iterate through cur_path one by one to form the new string (string is immutable).
Since this is the case at each step it’s O(n^2).
You can easily fix this by using a list instead of a string, which you can append to in constant time.
Still a helpful video!
You're (99%) right in that I should have used a string builder here because it's actually O(N) in the total runtime.
There's actually a very lesser known implementation in Python built into the CPython core library that if you do += with a string, it will actually concatenate in constant time. Though I forgot it needs to be += and just used + here to concat the strings. You can read about this here:
doc.pypy.org/en/latest/cpython_differences.html#performance-differences
Though yea I should have been more careful and most people (including interviewers) will probably not known or accept that 😂
@@crackfaang thank you so much! Just used this in my FAANG interview, they didn’t understand/know at first but they were definitely impressed I knew this. I wouldn’t have known without you!
@@jackkelley5409 Haha amazing! Yea it was a pretty clever solution I must admit. I really like these problems where you take some input and make a graph out of it so you can traverse it.
Hope you passed your interview!
This formulation to graph is brilliant, however the space and time complexity is still O(n), neverthless, it opens new way to solve problems.
Please let give him a thumbs up . He's doing a great job.
your explanation is amazing. Keep it up
That is a brilliant approach, very unique to what I have seen before! Good job!
Thanks! Glad you liked it, it was a fun one to solve
This is superb! I couldn't hold my breath seeing this awesome piece, yet given for free.
Thanks for the very kind words! Hope you find the same value from the other videos on the channel 😄
Wow! Should have found you on youtube earlier! The way you explain the solution is just concise, clean, and down to the point! Subscribed instantly!
Mate, big respect for such profound explanation - it definitely made me less scared of such examples!:) Keep up the good work, you are making community much better!
Thanks for this tutorial. This a good solution indeed. While there are other solutions for this problem that works with the original tree, transforming it first to undirected graph and then use a breadth-first search on the generated graph is a nice and neat solution and it does will help demonstrate the knowledge of trees and graphs for the student. It is also much cleaner, with code in two parts: creating the graph representation of the tree and then doing a bfs on the generated graph.
Thanks for the kind words! Make sure to subscribe so you don’t miss future uploads
One of the best and most beautiful explanations I've seen here. Good job
Another good solution. A similar question will be "All Nodes Distance K in Binary Tree"
Already solved it and uploaded a video 😉
Great solution ser. Really appreciate 🙏
This causes a memory limit exceeded in C++. Instead you could find the lowest common ancestor (LCA) and then just append the correct number of ‘U’s to the front of the path to destValue from the LCA.
Could be, I can only guarantee the solutions are accepted in Python. Though even with the official Leetcode solutions, due to the way they use dynamic cutoffs for the Time/Memory limits, even they can be TLE/MLE.
As long as you know the algorithm is correct and the time/space complexity is correct, doesn't matter if the judge accepts it or not. Sometimes Leetcode's judge just doesn't accept for strange reasons
There is another solution where you search from root to start node, then root to des node, and figure out how to combine those two paths to get the solution. My first approach was to do the bfs but it felt bad because we would end up storing so many different path strings
nice video, i have question about the space complexity ... why its not o(N + E) where N is number of nodes and E is the edges ? cas this graph is like adjacency list ? or i am getting it wrong ?
this is amazing .fast ,clean , simple - thank you
do you think there is a chance that the interviewer resist to do that in recursion ?
This is the iterative solution. Typically they will only ask you to rewrite a solution that was recursive if it's just too simple using recursion.
A common example is an inorder traversal of a binary tree using DFS. With recursion it's a one liner in Python. Iteratively it's much harder to implement and actually tests whether you understand how an inorder traversal works and how to use the stack correctly to do it.
Thanks
Just FYI, The same solution in Java returns TLE on Leetcode.
same for python
@@hassanali178 same for c++
Brilliant solution..
Thanks for the support! Make sure you subscribe so you don’t miss future videos
Wow great work!
Great job. Please increase the zoom or font size a bit
You are doing such a great job! Keep making videos!
would appreciate the most frequent Google questions
Working on it! Make sure you subscribe so you don’t miss when those videos come out
@@crackfaang do you mind telling me whats wrong with the js version?
var getDirections = function(root, startValue, destValue) {
let graph = {}
let stack = [root]
while(stack.length > 0) {
let currentNode = stack.pop()
if(currentNode.left) {
if(!graph[currentNode.val]) graph[currentNode.val] = []
graph[currentNode.val].push([currentNode.left.val, 'L'])
if(!graph[currentNode.left.val]) graph[currentNode.left.val] = []
graph[currentNode.left.val].push([currentNode.val, 'U'])
stack.push(currentNode.left)
}
if(currentNode.right) {
if(!graph[currentNode.val]) graph[currentNode.val] = []
graph[currentNode.val].push([currentNode.right.val, 'R'])
if(!graph[currentNode.right.val]) graph[currentNode.right.val] = []
graph[currentNode.right.val].push([currentNode.val, 'U'])
stack.push(currentNode.right)
}
}
let queue = [[startValue, ""]]
const visited = new Set()
visited.add(startValue)
while(queue.length > 0) {
let [node, path] = queue.shift()
if(node.val === destValue) {
return path;
}
for(neighbor in graph[node]) {
const [v, d] = neighbor
if(!visited.has(v)) {
queue.push([v, path+d])
visited.add(v)
}
}
}
return -1;
};
Could someone explain to me how we should intuitively know that BFS would give us the shortest path? This is a great solution btw!
Breadth first search through an undirected graph will always give the shortest path. It’s just a characteristic of breadth first search. Same how an I order traversal through a binary search tree gives all the nodes in sorted order
Great video! Does anyone have this solution in Javascript? I understand the logic, but having trouble implementing it in Javascript
This solution TLE in Python on 30th Nov 2022.
Hmm that’s fine, the leetcode judge does that sometimes when people submit enough. The solution is still valid though, there’s some questions where even the leetcode official solutions TLE
wow solution.. thanks a lot!
Thanks for the support! Make sure to subscribe so you don’t miss future uploads
Great solution, but when I did it in swift - I got "memory limit exceeded"
Sorry to hear you’re having trouble with the solution. Unfortunately I can only provide solutions which work in Python. And I personally would not recommend doing these questions in Swift. Most interviewers are unfamiliar with this language and unless you get someone who does iOS development, it might cost you the interview
Good vid, you should have more subs!
Thank you and I’m glad you are enjoying the content! I’m hoping to see some big growth soon
Hi I created a similar solution but i'm getting 'memory limit exceeded' error
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private class Pair{
int val;
String Path;
Pair(int val, String Path){
this.val = val;
this.Path = Path;
}
}
public String resultString(int root, int destValue, HashSet isVisited, HashMap graph, String curString){
if(isVisited.contains(root)){
return "";
}
isVisited.add(root);
if(root==destValue){
return curString;
}
for(Pair p : graph.get(root)){
String res = resultString(p.val, destValue, isVisited, graph, curString + p.Path);
if(res.length() > 0)
return res;
}
return "";
}
public String getDirections(TreeNode root, int startValue, int destValue) {
HashMap graph = new HashMap();
Queue q = new LinkedList();
q.add(root);
while(!q.isEmpty()){
TreeNode temp = q.remove();
if(!graph.containsKey(temp.val)){
ArrayListlist = new ArrayList();
graph.put(temp.val, list);
}
if(temp.left != null){
graph.get(temp.val).add(new Pair(temp.left.val, "L"));
ArrayListlist = new ArrayList();
list.add(new Pair(temp.val, "U"));
graph.put(temp.left.val, list);
q.add(temp.left);
}
if(temp.right != null){
graph.get(temp.val).add(new Pair(temp.right.val, "R"));
ArrayListlist = new ArrayList();
list.add(new Pair(temp.val, "U"));
graph.put(temp.right.val, list);
q.add(temp.right);
}
}
HashSet isVisited = new HashSet();
//System.out.println(hmap);
return resultString(startValue, destValue, isVisited, graph, "");
}
}
Can anyone here help me with this please
You don't need to create a Tree Node class or the Pair class. Though my solution is guaranteed to work in Python only. I don't know if the Leetcode judge will accept the same solution in a different language as there are different time and memory cutoffs based on the language
@@crackfaang Thank you 😊 really appreciate that you are taking your time to read my code and answer my query.
@@crackfaang Thank you will look into it
@@sharathkumar8338 did you get the accepted code?
@@joysagoo24 no