Rooting a tree | Graph Theory

How to root a tree at a particular node
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on UA-cam:
www.udemy.com/course/graph-th...
Algorithms repository:
github.com/williamfiset/algor...
Rooting tree source code:
github.com/williamfiset/Algor...
Video slides:
github.com/williamfiset/Algor...
0:00 Intro
0:26 How do root a tree
2:18 Rooting a tree pseudocode
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

[@mattm32]

Sir, Thank you so much. You have no idea how much time ur saving me.

[@kunal_chand]

Woohoo new upload!!

[@bingxie342]

Thanks, new videos yeah!

[@zss123456789]

It looks like if we wanted a balanced tree, then we could use the onion peeling algorithm to find the center of the graph, and use that as the root?

[@GotUpLateWithMoon]

buildTree() copy the parent-child relationship info from the adjacency list into the parent node then recursively into the child node

[@GotUpLateWithMoon]

It is necessary to check parent id is not null when rooting a tree is because:
A root may have null child then the child id is same as the parent id of root

[@ramkrishnakulkarni8289]

Is dfs more efficient than bfs in this case? Will there be any difference if we use bfs?

[@WilliamFiset-videos]

They'd be the same time complexity, but I'm almost certain the dfs implementation is much simpler.

[@tedarcher9120]

Dfs can convert a graph into a tree, but how do you find a good node to start dfs on?

[@123hunterHUNTER]

You could iterate through the list of all nodes in the graph and get the one that matches your conditions

[@tedarcher9120]

@@123hunterHUNTER that's probably gonna be quadratic

[@vijaybhatt8467]

Watch his finding tree center(s) video.

[@bingxie342]

How do select the designated node and make a balanced tree?

[@WilliamFiset-videos]

You could root the tree by either it's center or centroid?

[@suman6327]

if parent != null and childId == parent.id, this condition ensures we don't end up with cycles in Rooted Tree. Is my understanding correct ? If that's the case, imagine this combination : 3 -> 4, 4 -> 5, 5 -> 6, 6 ->3 this will create a cycle and our check with be futile right ?
My question is only to understand things better, thanks for sharing such great knowledge for free !!

[@sivajik]

Imagine like this. 3->4, 4->5, 5->6 and most importantly edge "5->4" Now your Node is "5", Parent is "4", Child is "6". When you are dealing with node "5" you have two children one is 5->6 and then 5->4. So we don't want to deal with 5->4 edge ad that would land you in a loop.

[@vikranttandon6253]

Basically, for this case since we have a 6->3 then there would have been a 3->6(because this is an undirected graph),
so, 6 will be placed as a child node under 3 and later when the control flow comes to 6->3 it'll be ignored.

[@aidejiushini]

Hey, thats what I have done in java
public TreeNode buildTree(TreeNode node) {
int[] children = graph.get(node.id);
List childrenNodes = new LinkedList();
for(int i = 0; i < children.length; i++) {
if(node.parent == null || (children[i] != node.id && children[i] != node.parent.id)) {
TreeNode treeNode = new TreeNode(children[i], node, null);
childrenNodes.add(buildTree(treeNode));
}
}
node.children = childrenNodes;
return node;
}

[@kaustuvakumarsahu3933]

is length the height of the tree.

[@aidejiushini]

@@kaustuvakumarsahu3933 no, you have to write the logic to determine the length of the tree