Beginner tree algorithms | Graph Theory

Beginner tree algorithms: tree height and leaf sum

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

Algorithms repository:

Next video (rooting a tree):

Video slides:

0:00 Intro
0:40 Problem 1: Leaf node sum
2:19 Problem 1: Pseudocode
3:32 Problem 2: Tree height
6:50 Problem 2: Pseudocode
8:25 Problem 2: Tree height simplification

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

[suyashmisra]

I'm sure you've heard this a lot before, but I must say that you teach a lot better than my DS professor. Keep up the good work, and stay safe!

[JustmeAgainOk]

This playlist will pass the test of time.

[niazahsan]

Appreciate the calmness of your voice.

[piyush]

Your videos are so well explained and easy to understand. Thanks for providing us such a high quality material

[simontai]

Really enjoy watching your videos, learnt a lot of things and a nice thing I would like to mention is the code quality, one function only do one thing even the logic can be written in one line, which make the code much more readable.

[remotetechie]

I don't do Java, so I really love that code is in pseudo <3

[DS-nrzc]

really enjoying this playlist during quarantine!

[BharCode]

Good to notice a video of recent time.. Thats some nostalgic music in the beginning! :) Thanks for making these great videos..

[mengyichen]

I have a question here 8:27
Still didn't get the idea why removing the leaf- checking base case is ok?
I think the statement of "correcting tree height" is not convincing.

[avoriginal]

What I don’t understand if you could please explain is why h-1 is used on every subtree, so for example, x root, go right have a z node, left of z node is another Y node, left of the Y node we have just a triangle (working on double rotation) which has a height of h-1, right of the Y node we have another triangle which has the height of h-2, right of Z node we have a triangle which is again h-1. Left of root x we have one triangle that is h-1, now where do these h-2 and h-1 come from. Also when checking the imbalance, a h+1 comes in to make it an imbalance of 2. How does this work, I can’t wrap my head around it. PLEASE HELP

[prashantbhrgv]

Hi William, Great videos! Really informative. Can you please share about how you create video slides?

[developmentarchive]

For the first problem, does it means that only rooted trees have leaves? Otherwise how can you traverse from a root node?

[sankalppatil]

Great video! This channel gives me 3blue1brown vibes.

[vijaybhatt]

Hi William, in the leafSum algorithm, you have one with the nodes with three children. I am assuming we would be using an adjacency list to store this tree. Please correct me if we have to do it differently.

[jackaus]

William must have a good taste of music. ;)

[cococu]

Hi William I have access to my company udemy account. I already bought the Graph Theory Algorithms course. However, I am not able to access the Easy to Advanced Data Structures. I guess it due to this course is different category which is not covered by my company. Would you be able to create a copy of "Easy to Advanced Data Structures" under "IT & Software
Other IT & Software
Algorithms", I believed many users are also facing the same issue. I can provide more details if requires. Hope you can help. Thanks.

[zarifmuhtasim]

couldn't you just loop through the nodes and sum up the values of the nodes whose out degree is 0?

[considerphi]

Actually it looks like he's copied your whole set of videos into a "course".

[avoriginal]

What I don’t understand if you could please explain is why h-1 is used on every subtree, so for example, x root, go right have a z node, left of z node is another Y node, left of the Y node we have just a triangle (working on double rotation) which has a height of h-1, right of the Y node we have another triangle which has the height of h-2, right of Z node we have a triangle which is again h-1. Left of root x we have one triangle that is h-1, now where do these h-2 and h-1 come from. Also when checking the imbalance, a h+1 comes in to make it an imbalance of 2. How does this work, I can’t wrap my head around it. PLEASE HELP