Graph Valid Tree - Leetcode 261 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Problem Link: neetcode.io/problems/valid-tree
0:00 - Read the problem
2:45 - Drawing Explanation
10:06 - Coding Explanation
leetcode 261
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#graph #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc

[@lasbutious116]

This was indirectly the best video explaining how to find a loop in an undirected graph

[@symbol767]

Wow, me just realizing that all this problem was is literally finding a loop in an undirected graph, damn.

[@lavanyam3224]

Not necessarily.. what if this is the case, edges are [0,1], [2,3], [3,4], [2,4].. Here the function returns False even though it has a loop (2,3,4).

[@staiwow]

if it has a loop, it should return false.

[@ladydimitrescu1155]

@@lavanyam3224 it should return False if it has a loop

[@tabassumkhan7498]

​@@lavanyam3224Here the graph contains 2 islands and maybe your code is not handling the unconnected components. For a graph to be a tree, it should not contain any loops and all the nodes should be connected. Since you are not accounting the unconnected component, the program will never reach the 2nd island where it has a loop. The program will finish after traversing 0 and 1 and will return true. To get around this, check if the size of the visited nodes == N. If not, return false. In your case, size of visited nodes should be 2 and hence should return false.

[@dpynsnyl]

Another use case of union find. In love with the algorithm!!

[@yashsrivastava677]

With your kind of explanation skills, I wish someday you create videos on System Design preparation videos.

[@leetcoderafeeq2641]

You must have future vision

[@tarastsugrii4367]

It's possible to solve this problem using basic tree properties - it's connected and has |V|-1 edges, so doing a single traversal to check if graph is connected combined with check that len(edges) == n - 1 should suffice.

[@BCS_AatirNadim]

but its also possible that one node is isolated, that way one loop has to exist in the graph, and this would return true even though the graph had a loop in it.

[@BCS_AatirNadim]

we can keep a check of all the n-1 numbered nodes, whether they have been visited or not

[@Nancy-gi9op]

@@BCS_AatirNadim I agree with Taras. The connected check ( if len(visited) == number_of_nodes) and edges check (len(edges) == number_of_nodes -1) should suffice. In the case that a node is isolated, the connected check would fail or if it is a single node with a self-loop, the edges check would fail.

[@nanakwamekankam1281]

I agree, but I think going through coding it out is good traversal practice. If anything, it helps the solver appreciate and understand this property of graphs more :)

[@sachinwalunjakar8854]

yes it possible, with union-find algorithm to check cycle and use property tree E = (V - 1) to check connectivity of graph.

[@danielsun716]

Since this problem is focusing on determine there is no cycle or not, so the first idea come up with me is using the Union find algorithm. Also, it can be solved with the normal DFS. Union-Find Solution: def valid_tree(self, n: int, edges: list): if n - 1 != len(edges): return False parent = [i for i in range(n)] rank = [1] * n def find(n): p = parent[n] while p != parent[p]: parent[p] = parent[parent[p]] p = parent[p] return p def union(n1, n2): p1, p2 = find(n1), find(n2) if p1 == p2: return 0 if rank[p1] > rank[p2]: parent[p2] = p1 rank[p1] += rank[p2] else: parent[p1] = p2 rank[p2] += rank[p1] return 1 res = n for n1, n2 in edges: res -= union(n1, n2) return res == 1

[@snoopyuj]

Can we just return false immediately when we meet the p1 == p2 condition?

[@danielsun716]

@@snoopyuj No. cause the return value of the nested function is int, not Boolean.

[@snoopyuj]

@@danielsun716 hmm... Maybe I can cache preRes to check that from outside. Thank you :)

[@danielsun716]

@@snoopyuj I do not think it can be broken into subproblems. But if you can do that, you could give a try.

[@snoopyuj]

@@AMKSD Good to know! Thanks!

[@michellewww8036]

very clear and I could learn DFS in a very logic way. Thanks!!!

[@BasicToAdvance_101]

Additionally it is mentioned in the constrained n is greater than or equal to 1 so we can omit the n==0 check

[@capooti]

excellent explanation as usual, thanks!

[@subhashreebanik8131]

Hey there! Firstly, your videos are AMAZING. I love watching your videos whenever I'm stuck. I can't thank you enough for existing Neetcode. Recently, I've found out that I get stuck on recursive solutions. I don't have much knowledge on recursion. What reading material would you suggest so that I can become a pro on recursion?

[@shadowsw8020]

Love this one, great explanation

[@LavanVivekanandasarma]

Really cool how the problem is a combo of Redundant Connection and Number of Connected Components In An Undirected Graph

[@AndroidNerd]

You deserve so many more views

[@leetcoderlandon8353]

Wonderful DFS approach ! My solution is to use BFS without tracking prev. Observation: In BFS, there is NO way we can form a cycle without 2 nodes from the same level. Cycle can only be formed by connecting two nodes in the same level, OR visiting a node more than once in a level (it has >=2 parents from the previous level). Either way, it requires two nodes from the same level be connected directly (when we have odd number nodes in a cycle) or indirectly (through a common offspring, when we have even number), together with the root we started from, they form a cycle. Another BFS solution thought I first have is to revisit a node from a offspring two levels after. It can be accepted and has the same time complexity. But it is slower, because we have to go at least 2 more levels before realizing we are actually in a cycle, compared to the first solution. Correct me if I am wrong. Thx guys!

[@leetcoderafeeq2641]

Another person who made a YT account just for leetcode. Do you work at google yet?

[@sk_4142]

could also run union-find to check for cycles and then return n - 1 == len(edges) to check for connectedness

[@saitejanagam5748]

Awesome explanation bro

[@shwethaks7994]

Your videos and explanations are just amazing. I was wondering if you can create some system design videos as well as it would be of great help to many people.

[@nikhilgoyal007]

self notes - Prev used to detect a cycle because it is an undirected graph.

[@jessanraj9086]

thank you so much

[@isseihyodou7111]

You can also, solve this by Union Find Algorithm Python: class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: par = [i for i in range(n)] rank = [1]*n conCom = n def find(n): p = par[n] while p != par[p]: par[p] = par[par[p]] p = par[p] return p def union(n1,n2): nonlocal conCom p1,p2 = find(n1),find(n2) if p1 == p2: return False if rank[p1] > rank[p2]: par[p2] = p1 rank[p1] += rank[p2] else: par[p1] = p2 rank[p2] += rank[p1] conCom -= 1 return True for n1,n2 in edges: if not union(n1,n2): return False if conCom != 1: return False return True

[@davidlee588]

After solving all NeetCode Graph problems in JavaScript, I just found that JS is not responsive every time to the same technique in DFS. For example: the construction of visit = new Set(); sometimes you have to add value.toString() in order to work out sometimes don't; most of the times you cannot establish this visit array, you just use grid[r][c] to keep track of the visited value. The union find is also problematic, esp. the find() method (sometimes you write p = par[n], sometimes you write p = n in the beginning)and the way you use union(), all variates according to different problems. What a weird and frustrating experience! I found DP easier to implement.

[@bchen1403]

For anyone that came from Redundant Connection, a little adjustment from that problem's solution can be applied here. if n == 1: return True if not edges or len(edges) < (n-1): return False With the above two lines added, you are good to go.

[@emmanuelromero2258]

How about Union Find Algo? # Union Find Algorithm def Solution(): def graphValidTree(self, n, edges): parent = [i for i in range(n)] ranks = [i for i in range(n)] # Build Find def find(n1): p = parent[n1] while p != parent[p]: parent[p] = parent[parent[p]] # Path Compression p = parent[p] return p # Build Union def union(n1, n2): p1, p2 = find(n1), find(n2) if p1 == p2: return False if ranks[p1] > ranks[p2]: ranks[p1] += ranks[p2] parent[p2] = p1 else: ranks[p2] += ranks[p1] parent[p1] = p2 return True for n1, n2 in edges: if union(n1, n2): n -= 1 else: return False return n == 0

[@roywastaken]

Doing God's work!

[@AshishSarin1]

Great explanation. Really easy to understand. Thanks

[@asifchoudhuryca]

Thanks!

[@BBRR442]

great video thanks, better at 0.75

[@zorali8219]

謝謝！

[@NeetCode]

Thank you so much, I really appreciate it! 😊

[@sachinwalunjakar8854]

It is possible solve this problem with time complexity O(E) using union-find algorithm to check cycle and using property of tree E = (V - 1) to check connectivity of graph.

[@vipinamar8323]

nodes = set() no_of_edges = 0 for i in edges: no_of_edges +=1 nodes.add(i[0]) nodes.add(i[1]) if no_of_edges < len(nodes): return True return False

[@iknoorsingh7454]

I guess we do not need to check the previous node conditions if we save the nodes as directed edges in the adjacency matrix. @neetcode?

[@pekarna]

4:40 - wouldn't an array of booleans of size N be more efficient than a hashset? We are going to end up with all of them in the set anyway, so array would be less memory and also marginally quicker to access.

[@timlee7492]

I have a dumb question . For example : in this example , when precessing node 1 and previous node is 0, then these two line of code' for j in adj[i] ; if j== previous' .That's mean prev node is 0, i=1, j=4. Are we comparing node 4 with node 0 instead of node 4 with node 1? Do I misunderstood anything there? Thanks! 🤔

[@krishnasharma657]

Can we do this by union join to Chek for loop and then checking if parent of each node is root to check for connected components??

[@tylera3126]

I was thinking the same thing

[@aaronhanson1694]

could we also do a union find algo? if number of components == 1 and no nodes share the same parent then were good?

[@dr4gonbloodx]

Yes

[@mahesh9762132636]

i tried this problem on directed and my approach didnt worked for undirected and when saw your video my respect for you using prev went through sky ...hats off to you bro

[@dingus2332]

Can we use union find to do this ?

[@TomerBenDavid]

Nice! Can you please tell which mic and drawing software you use? Affiliate links would be great way to support you on this thanks .

[@NeetCode]

Sure, this is the mic I use: amzn.to/2RRrLQd And I just use Paint3D for the drawings with a mouse.

[@TomerBenDavid]

@@NeetCode thanks! I read a little bit about this mic I think this is really great choice from what I saw then this mic is comparable to blue yeti but has less base I think this only contributes to the clarity of voice! so it's better in that manner than blue yeti. I'm pretty surprised your are able to write letters pretty precisely with mouse. On top of all the explanations are brilliant (so even with the worst mouse/mic you would still rule the explanations) but somehow the clarity of this mic + drawing + the brilliant undoing of drawing while drawing to keep screen clear is a winning combination on top of the super clear brilliant explanations.

[@johnscherian9925]

Not sure if this is the right place for this question. Interviewing for a Solutions Architect role. Have not coded fundamentals in a while. Wondering if given a position for the car how to get the associated string for example, If given the car is at position 25, what string sequence(s) would allow a car to achieve this position, the second part of the following question. I know from the problem statement/example, this would be achieved by AAAAARAAARA. However could other strings be obtained and how could i generate all this in code- what algo and ds should be considered, naive first and then optimized. Thanks! A (fictional) early version of self-driving car had some limitations: it could only travel in a straight line, and it was pre-programmed with a sequence of instructions from an instruction set of two. The two instructions are: [A]ccelerate: move in the current direction for one second, then double your speed. [R]everse: stop immediately, change direction, then reset your speed. The initial speed, and the speed after a Reverse instruction, is 1 unit per second So, for example, the sequence AAAAARAAARA moves the car (1+2+4+8+16)-(1+2+4)+(1) = 25. f(AAAAARAAARA) a) Take a sequence string and produce the final position def position(sequence): final_pos = 0 speed = 1 for command in range (len(sequence)): if sequence(command) == “A”: final_pos = final_pos + speed speed = speed * 2 else sequence(command) == “R”: speed = -1* speed/abs(speed) return final_pos b) Second part, given position get string Thanks for your feedback!

[@ameynaik2743]

Great video, is there any advantage of using dfs instead of bfs?

[@NeetCode]

No, I think either one is fine. I'm more use to DFS but sometime BFS can make problems easier.

[@shan504]

why is the complexity O(e+v)?? if you visit each node once it should be O(v) right? going to an already visited node results in an immediate return of O(1)

[@dorondavid4698]

He's using an Adjacency list, so for every V you have to visit all of its E (to get to the other V)

[@lomoyang3034]

I'm not sure if this solution works. Think about A->B, B->C, C->A, in this case, A is C's neighbor, but not C's prev. but there is a loop, and it's not a tree. Please correct me if I'm wrong.

[@jessepinkman2942]

It would return false because A, and B would already be in the visited set when you visit C. So when you visit C's neighbor then you would encounter A (or B) and since it is already visited then a cycle has been detected.

[@romangirin772]

this problem could be solved via DSU (disjoint set union)

[@sushantrocks]

Check connected and n=e+1?

[@annsway]

If possible, would you please explain line 25 - 26 in your code? I don't understand why dfs(j, i) should be in the if condition.

[@yuemingpang3161]

to check if there is a loop. If there is a loop then return false and it is not a tree. To be a tree, all the "if" loop detection guards need to be skipped during recursion and return true at the end.

[@gourishpisal2796]

what is the use of adj list?

[@niloofaryousefi1757]

great explanation :) I was just wondering why this problem cannot be solved using UnionFind algorithm ? can anyone help, please!

[@ianalexthompson]

Surely, It can be done that way. It's just one of possible solutions

[@madhumithakolkar_]

Which part of this takes care of the condition of having a node that isn't connected to the rest of the nodes ?

[@chitii91]

return dfs(0, -1) and "len(visited) == n"

[@EduarteBDO]

After all prev questions being union find I didn't even though of dfs and did union find solution: class Solution: def valid_tree(self, n: int, edges: List[List[int]]) -> bool: if len(edges) < n-1:return False par = [i for i in range(n)] rank = [1] * n def find(n): while n != par[n]: par[n] = par[par[n]] n = par[n] return n def union(n1:int, n2:int): r1, r2 = find(n1), find(n2) if r1 == r2:return False if rank[r1] > rank[r2]: par[r2] = r1 rank[r1] += rank[r2] else: par[r1] = r2 rank[r2] += rank[r1] return True for n1, n2 in edges: if not union(n1, n2): return False return True

[@axellbrendow1]

What happens if the root node is not node 0 ? This implementation assumes node 0 is not a leaf for example.

[@petersiracusa5281]

in a tree, any node can be treated a root. It will still be acyclic and connected. try redrawing any tree with some other node as root. Can always be done.

[@axellbrendow1]

@@petersiracusa5281 I forgot that the question states the edges are undirected. If the edges were directed, my comment would make sense.

[@gokusaiyan1128]

union find would have been better/easier approach for this problem

[@algorithmo134]

Can you do binary tree cameras please Neetcode? 😭

[@NeetCode]

I took a look at the problem, I havent solved it before but I will try to do it eventually, but maybe not soon.

[@gourishpisal2796]

why are we using it?

[@fishoil5310]

I'm not sure why but it seems that I need to have both of these conditions to pass the test cases if n==1: return true if n>0 and len(edges)==0: return false

[@leventoz9530]

I don't see where in the problem it says 0 is the root node.

[@user-kb6zs9wf8d]

the is no root, the nodes are labeled from 0 to n-1

[@iambao1940]

class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: if len(edges) != n - 1: return False if n == 1: return True nodes = set() for e in edges: nodes.add(e[0]) nodes.add(e[1]) return len(nodes) == n This code works

[@jonaskhanwald566]

how to code recursively.

[@rishikaverma9846]

one testcase doesn't display the desired outcome

[@tinymurky7329]

I found out union find can work class Solution: """ @param n: An integer @param edges: a list of undirected edges @return: true if it's a valid tree, or false """ def valid_tree(self, n: int, edges: List[List[int]]) -> bool: # write your code here id = [i for i in range(n)] self.n = n def find(v): if v != id[v]: root = find(id[v]) id[v] = root return root else: return v def union(a, b): rootA = find(a) rootB = find(b) if rootA == rootB: return False else: id[rootA] = rootB self.n -= 1 return True for a, b in edges: if not union(a, b): return False if self.n != 1: return False return True

[@alfahimbin7161]

Anyone having problem with Lintcode login??

[@eyeamkd]

Takes 20.80MB to run..."eFfiCientLY"

[@MaxFung]

this mf always does dfs

[@BBRR442]

why does guy sound passively mad

[@oliverduan1374]

LeetCode, LintCode and NeetCode, lol

[@mushahidkhan7472]

Dont take this the wrong way but you shouuld just state the complexities yhou should rather explain them. DOnt just say its O(E+V) rather explain why we are using E+V and why is it? I am thinking time complexity should just be O(E) where E is number of edges. It takes O(E) to make adjacency list and then it takes O(E) to visit all edges(in other words we do E number of recursion calls, i dont understand why the number of vertices matters here) and the space complexity is O(number of vertices * number of edges) because in worst case, we can have a fully connected graph input and so the dictionary has keys equal to number of vertices and for each vertex key in the dictionary, we have a list of edges.