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! :)
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.
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
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) ```
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.
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
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.
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()
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.
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
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++;
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
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:]
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! :)
I had exactly the same problem! Thanks for the explanation.
same
Yeah
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.
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
how you converted in a graph?!
i wanted to do this but didnt knew how
@@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
@@sayanbiswas2116 We mark the parents of each node with the help of hashmap so we could move in up direction also
@@sayanbiswas2116 store parents in map and while doing left and right traversal also do parent traversal of parent!=null
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)
```
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.
Yeah I guess that's the only downside of python, more strict acceptance criteria.
Ive seen really inefficient solutions pass with c++ for example
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
I literally feel blessed to have you. Hail NeetCode! Long live NeetCode. 😇
Another great explanation. Thank you !
And here i did DFS on tree by storing parent pointer , couldn't came up with this smart solution
Great explanation, Thank you !
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.
I use paint 3d with mouse and streamlabs obs for screen capture. I use Windows 11
@@NeetCodeIO Much appreciated. Thank you for the response. Do you use Screen pen to write on an image? or using mouse for that too?
Brilliant! Thanks!
Such a masterpiece!
This question was pretty good.
Dear neetcode, please make a video on LCA of binary tree 🙏
why cant you make some videos on trees in python ? that may help us really a lot
he did a lot of tree-problem videos actually.
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
Just released it last night. Will prob add one or two more sections for math & misc topics.
Its a very good solution
Any difference between doing BFS and DFS? My answer is pretty much the same but I'm in the second bellcurve of the runtime
are you using BFS instead?
@@corrogist692yeah I’m using BFS, solution is pretty much the same just runtime I’m very behind on the LC statistics
I tried it with the lowest common ancestor but wasn't able to figure out how to get that string😅
I tried the same bro.
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)
Such a good solution
Glad it's helpful :)
@@NeetCodeIO this was asked to me in interview today and I was so happy. Thanks alot
@@dishagupta7446 OH that;s great!
I got the solution but was getting memory limit exceeded ☹️
same
@@aashishbathe I got the same initially because of string manipulation. Then converted code to use array which solved the issue.
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.
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
dont set add in very begining it hangs
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;
}
}
❤
i got it with a dfs + bfs solution and actually came up with ur solution but got MLE 😭
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
Lol.... do the same. DAMN. Thing..... I like you bro.....
you are early today 😂
bro got carried away lol
Damnn
damn🤣🤣🤣🤣
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
for god pls let give copy of your code in description otherwise I will quit coding one day
Lol
First!
i will appreciate if you giv your python to copy
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:]