Step-By-Step Directions from a Binary Tree Node to Another - Leetcode 2096 - Python

[@yuvarajyuvi9691]

I converted the tree to a graph and did a bfs, I thought it couldn't be solved with a trivial tree traversal, but this is pretty smart solution. I haven't thought of this

[@sayanbiswas2116]

how you converted in a graph?! i wanted to do this but didnt knew how

[@DeathSugar]

@@sayanbiswas2116 just put it in queue/stack. but not sure how he did it with bfs. it should eat O(n) memory if he managed to make it

[@_sf_editz1870]

@@sayanbiswas2116 We mark the parents of each node with the help of hashmap so we could move in up direction also

[@phantomhawk489]

​@@sayanbiswas2116 store parents in map and while doing left and right traversal also do parent traversal of parent!=null

[@33galactus]

You can either store parent of each node in a hashmap OR in Python simply add parent pointer to the node object itself. Then simply run BFS from startNode. Each node will have three neighbors (node.left, node.right, node.parent). Here is the code snippet to add the parent pointer (and find the startNode).: ``` # create a parent pointer for each node def createParentPointer(node, p): nonlocal startNode if node.val == startValue: # find startNode = node node.parent = p if node.left: createParentPointer(node.left, node) if node.right: createParentPointer(node.right, node) startNode = None createParentPointer(root, None) ```

[@thewalkingsnail]

I implemented this algo but was getting "Memory limit exceeded" errors on the 287th test case because I used a string for the path instead of a list like he does here. If you see "Memory Limit Exceeded" switch to a mutable list instead of (I guess) duplicating the path string at each recursive case! :)

[@reactionchamber]

I had exactly the same problem! Thanks for the explanation.

[@tunno4586]

same

[@rajavignesh7216]

Yeah

[@woodylucas]

The process needs to be changed by doing BFS using a queue, which can be implemented iteratively. This avoids the risk of stack overflow, making it more memory-efficient for large or unbalanced trees. BFS also has the advantage of finding the shortest path in terms of edge count, which aligns well with our goal of finding the shortest direction path.

[@arunpranavat]

I literally feel blessed to have you. Hail NeetCode! Long live NeetCode. 😇

[@finemechanic]

Technically you shouldn't have used recursion in this problem because the description tells the maximal n is 10**5 and in the worst case you will hit the default Python recursion limit (which is 1000 as I recall). They at Leetcode shall either make a testcase against recursive solution or provide a guarantee on the maximal tree height.

[@NeetCodeIO]

Yeah I guess that's the only downside of python, more strict acceptance criteria. Ive seen really inefficient solutions pass with c++ for example

[@MP-ny3ep]

Another great explanation. Thank you !

[@abhishekkumar-fe8lw]

class Solution { public String getDirections(TreeNode root, int startValue, int destValue) { String startPath=dfs(root,startValue,new StringBuilder()); String destPath=dfs(root,destValue,new StringBuilder()); StringBuilder ans=new StringBuilder(); int i=0; while(i

[@sergei200110]

Great explanation, Thank you !

[@kumarsanu2499]

And here i did DFS on tree by storing parent pointer , couldn't came up with this smart solution

[@neks2081]

Dear neetcode, please make a video on LCA of binary tree 🙏

[@drishtirajai7848]

Such a masterpiece!

[@Cheng-K]

Brilliant! Thanks!

[@_sf_editz1870]

Its a very good solution

[@dishagupta7446]

Such a good solution

[@NeetCodeIO]

Glad it's helpful :)

[@dishagupta7446]

@@NeetCodeIO this was asked to me in interview today and I was so happy. Thanks alot

[@NeetCodeIO]

@@dishagupta7446 OH that;s great!

[@AnordinaryMan007]

This question was pretty good.

[@MustafaAlqaseer-y9d]

Hey! I'm a new sub to the neetcode course and I'm wondering when will the "python coding for interviews" course coming out? Thanks

[@NeetCodeIO]

Just released it last night. Will prob add one or two more sections for math & misc topics.

[@GauravKumar-qe7iu]

JAVA Solution: class Solution { public static String start; public static String dest; public String getDirections(TreeNode root, int startValue, int destValue) { start = null; dest = null; helper(root, startValue, destValue, new StringBuilder()); StringBuilder res = new StringBuilder(); int i = 0; int minLen = Math.min(start.length(), dest.length()); while (i < minLen && start.charAt(i) == dest.charAt(i)) i++; for (int j = i; j < start.length(); j++) res.append("U"); for (int j = i; j < dest.length(); j++) { res.append(dest.charAt(j)); } return res.toString(); } private boolean helper(TreeNode root, int startValue, int destValue, StringBuilder tmp) { if (root == null) return false; if (root.val == startValue) start = tmp.toString(); if (root.val == destValue) dest = tmp.toString(); if (start != null && dest != null) return true; tmp.append("L"); if (helper(root.left, startValue, destValue, tmp)) return true; tmp.setLength(tmp.length() - 1); tmp.append("R"); if (helper(root.right, startValue, destValue, tmp)) return true; tmp.setLength(tmp.length() - 1); return false; } }

[@brayn7504]

Hello, could you please tell me tools or devices you use in order to edit your videos? I wanted to know how to write on top of screen to explain your reasoning while recording. Thank you.

[@NeetCodeIO]

I use paint 3d with mouse and streamlabs obs for screen capture. I use Windows 11

[@brayn7504]

@@NeetCodeIO Much appreciated. Thank you for the response. Do you use Screen pen to write on an image? or using mouse for that too?

[@reb6482]

Any difference between doing BFS and DFS? My answer is pretty much the same but I'm in the second bellcurve of the runtime

[@corrogist692]

are you using BFS instead?

[@reb6482]

@@corrogist692yeah I’m using BFS, solution is pretty much the same just runtime I’m very behind on the LC statistics

[@nanicreations7729]

❤

[@GundeboinaDheeraj]

why cant you make some videos on trees in python ? that may help us really a lot

[@slizverg23]

he did a lot of tree-problem videos actually.

[@pastori2672]

i got it with a dfs + bfs solution and actually came up with ur solution but got MLE 😭

[@aashishbathe]

I got the solution but was getting memory limit exceeded ☹️

[@pratyushthakur8478]

same

[@pratikpatel2512]

@@aashishbathe I got the same initially because of string manipulation. Then converted code to use array which solved the issue.

[@sidazhong2019]

Same man, HOWEVER, I featured it out! I was using dfs(path + ["R"]) to avoid backtracking, I supposed you did too. That's the reason you got memory exceeded, it's actually stack overflow.

[@maanas_sehgal]

I tried it with the lowest common ancestor but wasn't able to figure out how to get that string😅

[@pratikpatel2512]

I tried the same bro.

[@thunderstorm-d2c]

The string part is a little bit tricky, and certainly make it more like a backtracking question. I separated the conditions to three. 1. The LCA is the start node, traverse from the LCA to the end node and append ''L" or "R' based on the path choice. 2. The LCA is the end node, traverse from the LCA to the start node and append ''U", since it is always going up. 3. The LCA is in the middle, it is the combined situation of the two described above. You need to go to the end node from the LCA(append 'R' or 'l' in path), and goes from the LCA from the start node (append 'U' in path). Certainly the code is not as good as what nc provided in the video, and takes a long time to code. class Solution: def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str: def lca(root,lv,rv): if not root: return None if root.val == lv or root.val == rv: return root lr = lca(root.left,lv,rv) rr = lca(root.right,lv,rv) if lr and rr: return root else: if lr: return lr elif rr: return rr else: return None node = lca(root,startValue,destValue) def traverse(node,nv,flag,path): if not node: return False if node.val == nv: return True if flag != 'U': path.append('L') lr = traverse(node.left,nv,flag,path) if lr: return True path.pop() path.append('R') rr = traverse(node.right,nv,flag,path) if rr: return True path.pop() else: path.append('U') lr = traverse(node.left,nv,flag,path) if lr: return True rr = traverse(node.right,nv,flag,path) if rr: return True path.pop() return False path = [] if node.val == startValue: traverse(node,destValue,'D',path) return ''.join(path) elif node.val == destValue: traverse(node,startValue,'U',path) return ''.join(path) else: p1 = [] p2 = [] traverse(node,startValue,'U',p1) traverse(node,destValue,'D',p2) return ''.join(p1 + p2)

[@iuri0072]

for some reason, in my code, it didn't return as yours... it was returning as a list. to solve it, i had to rewrite as: return "".join(["U"] * len(startPath[i:]) + destPath[i:]) but ok... it worked in the end

[@TheModernSamurai]

Lol.... do the same. DAMN. Thing..... I like you bro.....

[@GeetainSaar]

dont set add in very begining it hangs

[@jayrathod9271]

Non recursve solution def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str: leftPath,rightPath='','' is_left,is_right=False,False st=[[root,'']] while len(st)>0 and (not is_left or not is_right): node,curr=st.pop() if node.val==startValue: leftPath = curr is_left=True print('reach start') if node.val==destValue: rightPath = curr print('reach dest') is_right=True if node.left: st.append([node.left,curr+'L']) if node.right: st.append([node.right,curr+'R']) i,j = 0 , 0 n,m = len(leftPath),len(rightPath) while i

[@_sf_editz1870]

i coded the same in java but its giving tle class Solution { //NeetCode public String getDirections(TreeNode root, int startValue, int destValue) { String a = generatePaths(root , startValue , ""); //startPath String b = generatePaths(root , destValue , ""); //endPath //we just need to skip the part until the LCA and replace U in startPath int i=0; while(i

[@floatingpoint7629]

you are early today 😂

[@pratikpatel2512]

I came up with the same solution. I extracted the path to the start and destination in a single pass and rest the same. class Solution: def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str: path = [] self.root_to_start = "" self.root_to_dest = "" def dfs(node, start, dest): if node.val == start: self.root_to_start = "".join(path) if node.val == dest: self.root_to_dest = "".join(path) if self.root_to_start and self.root_to_dest: return if node.left: path.append('L') dfs(node.left, start, dest) path.pop() if node.right: path.append('R') dfs(node.right, start, dest) path.pop() dfs(root, startValue, destValue) len_start_path = len(self.root_to_start) len_dest_path = len(self.root_to_dest) idx = 0 while len_start_path > idx and len_dest_path > idx: if self.root_to_start[idx] != self.root_to_dest[idx]: break idx += 1 return "U" * (len_start_path - idx) + self.root_to_dest[idx:]

[@RK-cd]

Damnn

[@TenzDelek]

bro got carried away lol

[@GeetainSaar]

for god pls let give copy of your code in description otherwise I will quit coding one day

[@glasskey_]

Lol

[@mdrashedulhasanmr8456]

damn🤣🤣🤣🤣

[@shashanksreepathi7184]

First!

[@GeetainSaar]

i will appreciate if you giv your python to copy