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) ```
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.
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.
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.
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++;
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()
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
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 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)
```
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.
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
I literally feel blessed to have you. Hail NeetCode! Long live NeetCode. 😇
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
Another great explanation. Thank you !
Great explanation, Thank you !
Brilliant! Thanks!
Such a masterpiece!
Dear neetcode, please make a video on LCA of binary tree 🙏
And here i did DFS on tree by storing parent pointer , couldn't came up with this smart solution
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
This question was pretty good.
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!
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.
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?
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 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.
❤
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 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)
i got it with a dfs + bfs solution and actually came up with ur solution but got MLE 😭
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
Lol.... do the same. DAMN. Thing..... I like you bro.....
you are early today 😂
Damnn
bro got carried away lol
dont set add in very begining it hangs
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
First!
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
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:]