STEP-BY-STEP DIRECTIONS FROM A BINARY TREE NODE TO ANOTHER | PYTHON | LEETCODE # 2096

In this video we are solving Leetcode Problem # 2096: Step-by-Step Directions from a Binary Tree Node to Another. This is a popular Google interview question at the moment and is definitely a good interview question which tests your knowledge of both tree and graph traversals.

[@symbol767]

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

[@crackfaang]

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.

[@symbol767]

@@crackfaang Text Justification on Leetcode, one of Googles most asked questions, its insane

[@leokim1463]

@@crackfaang it would be great if you could add 1284 to your queue. I assume your queue is not a priority queue :D

[@markomekjavic]

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!

[@emmanuelonah4596]

This is superb! I couldn't hold my breath seeing this awesome piece, yet given for free.

[@crackfaang]

Thanks for the very kind words! Hope you find the same value from the other videos on the channel 😄

[@jeromeeusebius]

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.

[@crackfaang]

Thanks for the kind words! Make sure to subscribe so you don’t miss future uploads

[@Anthro12011fall]

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!

[@JaydenMomos]

That is a brilliant approach, very unique to what I have seen before! Good job!

[@crackfaang]

Thanks! Glad you liked it, it was a fun one to solve

[@ugochukwustephenmbonu7974]

One of the best and most beautiful explanations I've seen here. Good job

[@jackkelley5409]

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!

[@crackfaang]

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 😂

[@jackkelley5409]

@@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!

[@crackfaang]

@@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!

[@SethuIyer95]

This formulation to graph is brilliant, however the space and time complexity is still O(n), neverthless, it opens new way to solve problems.

[@asdfgsf9660]

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.

[@crackfaang]

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

[@TheKillermob13]

this is amazing .fast ,clean , simple - thank you do you think there is a chance that the interviewer resist to do that in recursion ?

[@crackfaang]

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.

[@themagickalmagickman]

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

[@mohamed44324]

your explanation is amazing. Keep it up

[@BBRR442]

Wow great work!

[@eddiej204]

Great solution ser. Really appreciate 🙏

[@ebenezeracquah478]

Please let give him a thumbs up . He's doing a great job.

[@enisarik6002]

Brilliant solution..

[@crackfaang]

Thanks for the support! Make sure you subscribe so you don’t miss future videos

[@neeldesai108]

Just FYI, The same solution in Java returns TLE on Leetcode.

[@hassanali178]

same for python

[@anirbanpal9432]

@@hassanali178 same for c++

[@zoompie6786]

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 ?

[@MinhNguyen-lz1pg]

Another good solution. A similar question will be "All Nodes Distance K in Binary Tree"

[@crackfaang]

Already solved it and uploaded a video 😉

[@prateekgoyal3353]

wow solution.. thanks a lot!

[@crackfaang]

Thanks for the support! Make sure to subscribe so you don’t miss future uploads

[@subee128]

Thanks

[@kevingonzalez9790]

would appreciate the most frequent Google questions

[@crackfaang]

Working on it! Make sure you subscribe so you don’t miss when those videos come out

[@kevingonzalez9790]

@@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; };

[@umaimakhurshidahmad1939]

You are doing such a great job! Keep making videos!

[@_7__716]

Great job. Please increase the zoom or font size a bit

[@cheesehead6982]

Good vid, you should have more subs!

[@crackfaang]

Thank you and I’m glad you are enjoying the content! I’m hoping to see some big growth soon

[@rovaldyapplyrs3918]

Could someone explain to me how we should intuitively know that BFS would give us the shortest path? This is a great solution btw!

[@crackfaang]

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

[@aubreyselamu-bell390]

Great video! Does anyone have this solution in Javascript? I understand the logic, but having trouble implementing it in Javascript

[@saniramadzhikova8382]

Great solution, but when I did it in swift - I got "memory limit exceeded"

[@crackfaang]

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

[@SmoothCode]

This solution TLE in Python on 30th Nov 2022.

[@crackfaang]

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

[@sharathkumar8338]

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

[@crackfaang]

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

[@sharathkumar8338]

@@crackfaang Thank you 😊 really appreciate that you are taking your time to read my code and answer my query.

[@sharathkumar8338]

@@crackfaang Thank you will look into it

[@joysagoo24]

@@sharathkumar8338 did you get the accepted code?

[@sharathkumar8338]

@@joysagoo24 no