Tree center(s) | Graph Theory

How to find the center node(s) of tree

Algorithms repository:

Video slides:

Video source code:

===================================

Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on YouTube:

[imabstrong]

Your solution is basically a multi-source BFS. To make it more explicit, here's a psuedocode using a queue:

function treeCenters(g):
n = g.length
degree = [0]*n
q = Queue()
for (i = 0; i < n; i++):
degree[i] = g[i].length
if degree[i] == 0 or degree[i] == 1:
q.enqueue(i)
degree[i] = 0

count = q.size
while count < n:
for (_ = 0; _ < q.size; _++):
node = q.dequeue()
for neighbor in g[node]:
degree[neighbor]--
if degree[neighbor] == 1:
count++
q.enqueue(neighbor)
degree[node] = 0
return q


The basic idea is to first enqueue all the leaf nodes, prune it, then enqueue all the next layer nodes with the lower degree, etc.

[jagrit]

I watched this video few months back and was not able to grasp much. But then today as I was solving a few questions on LeetCode related to graphs, I came across this question, LC 310. Minimum Height Trees, where we need to return the possible value of roots so that tree is of minimum height. I gave it a dry run and concluded that I needed centre (s) and as I have watched the video way back, I had some idea that we can find the centre if we want so I watched it again and was able to solve the question. I just wanted to thank you for this series and especially the Github codes. And anyone who is finding this series difficult in first time, do watch his videos twice or thrice.

[coypirus]

Saw some people wondering why the algorithm terminates at count < n and not count < n-2, so I figured I should post my personal explanation.

I believe it is because count keeps a running total of the amount of nodes that have become/are leaves. When the algorithm removes the current leaf nodes, it finds the newly formed leaf nodes and adds them to the count. Therefore, on the last iteration, when it removes nodes so that only the center nodes are left, the center node(s) will have become leaf nodes. In the case where there is one center, before the removal of the last non-center leaf node, the center will only be connected to one node thereby being a leaf node, and in the case where there are two centers, the centers will be leaf nodes when all other nodes are removed because the centers are connected to each other. In either case, at that point, the running total "count" will be n, terminating the loop.

[aminuolawale]

Bobbing my head rhythmically at the beginning of every video. Sick intro.

[sumant]

I guess 'degree[i] = 0' (not in if- statement) and 'degree[node] = 0'
are redundant since we aren't using them anywhere.

[shashanksingh-fqwy]

in case of lc 310, it only worked when i did while count_of_nodes_visited < n - 2:
and not count_of_nodes_visited < n

[atmadeepchanda]

Thanks a lot for ur effort. U really have made all these topics quite simple to understand.

[simon.p]

What would be the time complexity for this algorithm? It seems like the first for-loop that calculates the initial set of leaves is O(V), and the while-loop runs in O(V+E) = O(V + V - 1) = O(V). Thus the overall complexity is just O(V). Is this correct?

[GotUpLateWithMoon]

There are two phases in this algorithm: 1. building the degrees(and collecting the first group of leaves). 2. peeling the leaves.
I confused on why aren't the degree[i] = 0 in the building phase and the degree[node] = 0 in the peeling phase are repetitive? Shouldn't only one is needed?

Answer to my own question: because the second assignment can only work on the new leaves, not the initial ones.

[kongzilla]

Wow! very clean explanation, Thank you :)

[cmkjfnve]

Hi! Thanks for video :-)
Do you take care of already pruned/removed nodes when getting neighbours?
Nodes with degree 0 should be excluded from further processing. Either they should removed from the graph or their degree should be checked when iterating over neighbours. For example we could skip a node if its deg is 0 in the inner for-loop.

[daumtto]

just curious, will there be a condition degree[i] < 0 == true, when all processed? Because you are not checking the degree[neighbor] < 0? I think we are going to process the leaf node again because in degree[neighbor] = degree[neighbor] - 1, the neighbor can be the leaf node we processed before.
I know degree[node] isn't that important, but if trying to give meaning of code, I think it's still important. Thank you.

[UmaShankar-kxek]

Once we have calculated the degree of each node, Is there reason why we cannot just select the node with highest degree as the center? I think I'm missing something here as no one else has asked it. With assumption that I'm storing degree of each node say in a map along with reference to node.

[anthonylee]

Could you help to explain why the stop condition is (count < n)? why it's not count < n-2 since we should stop when we get to the last one or two nodes?

[priyanka.sarkar]

Such an amazing problem and an even more amazing explanation. Thanks for such great videos. Just one point, do we really need to set degree[i] = 0 in the first for loop's if condition where we are finding the degree's of the nodes in the graph ( tree ) ? Isn't it being taken care in the while loop by default ? Because in the while loop we are processing the list of nodes with degree 1 (essentially the leaf nodes at each layer) and setting it's degree to 0 after visiting all it's neighbours. Also is this setting required ?

[ik]

should n't the while condition be
while (count > 2)
instead of
while (count < n) ?

SInce the tree can have atmost 2 centers

[upsolvecontest]

If this is a directed graph then what happens

[suman]

Willaim, thanks a ton for these high quality videos. One question, when a graph represented as an Adjacency List is given and asked to create a Tree out of it. Do we first need to find the center node (this video) and then apply Rooting a Tree algo (previous video) ?? Or my understanding is completely wrong.

It would help if you can elaborate on this, thanks.

[HamidBazargani]

Great video. In 3:27 I think there's no need to do `degree[node] = 0`

[aidejiushini]

hey, I think it is redundant when you put this line "for (neighbor : g[node])" in the loop, your g[node] is a leaf and has already been one neighbor, so you don't need to put it in the loop, people will be confused.