Find Height of a Binary Tree (Algo + Code + Complexity)

Подписаться 582

Просмотров 41 тыс.

50% 1

This video will show you how to find the height of a binary tree.
We will first go through the algorithm, then write the code, and finally, analyze the time and space complexity.
What is the height of a binary tree?
The height of a binary tree is the largest number of edges in a path from the root node to a leaf node.
How can we find it?
The algorithm to find the height is very simple: we start at the root node and find the height of the left subtree, then the height of the right subtree, and finally, we return the maximum of the two heights plus one.
You can find the C++ code for the height function shown in the video by going to cs.phyley.com/binary-tree/find-height

Опубликовано:

11 апр 2018

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 32

@gasparstudios3021 5 лет назад

Thank you for taking the time to do this. Man, I've spent days looking for something like this video. This video explains in detail what's happening behind the scenes with recursion in trees. It takes patience, focus, paper and pencil to fully understand. 5/5

@varunmodak6100 3 года назад

Yo this video was so detailed and well explained. Looked so long for a video that covers the algorithm extensively, and you do an amazing job! Thanks a ton.

@boshiij3449 4 года назад

going through the code step by step really helped me understand. Thank you so much!

@emmanuelezeka7236 2 года назад

Yo, your video is amazing. Like I couldn't move on without visualizing what you shared in this video. Thanks and I am looking forward to equivalent content in other parts of DSA.

@AudiA435R 5 лет назад

Very helpful thank you, I was conceptually stuck trying to figure out how this worked.

@BluetonicUK28 4 года назад

Love this, thank you. It has gone some way to helping me with recursion in general.

@adebs 4 года назад

thank you for stepping through an example! so helpful!

@chestermartin2356 2 года назад

Most helpful video yet, still not clicked with me yet but I feel about 10 steps further now

@chestermartin2356 2 года назад

Although I went back to rewrite my method and immediately understood it so great success :D thank you

@jazz4dayz543 5 лет назад

Thanks for the upload. Even debugging that code from the stack overflow post I couldn't really fully understand what was happening x_x this helped a lot.

@gabrielalmeida8584 8 месяцев назад

The best video on youtube about it. Thank you

@waynefong5960 3 года назад

Thank you for the video. This helped me to solve one of the question in my assignment. Keep going!

@quannguyenhahong168 Год назад

Thank you, great explanation!

@timr1810 6 лет назад

also, when I see algorithms for checking if the tree is balanced they change the meaning of height and use -1 to indicate a non-balanced height. they use a 0 height for null node. I realize this is a trick to reduce the O() complexity of the algo, but it kindof goes against the grain to have a method getHeight(Node root) that doesn't actually return the height. Do you have a algo that determines if a tree is balanced?

@jnyfah 3 года назад

Spot on!!

@danielshahverdi7053 6 месяцев назад

Thank you for making this video🙏🙏

@QUITEthegamer Год назад

really good explanation

@timr1810 6 лет назад

I like your video , algorithm and explanation. Is this a legal binary tree? how would you add node values to git this tree?

@ishasaikumar868 4 года назад

thank you

@reshsajitalks9843 Год назад

Best explanation

@endfine9230 3 месяца назад

best explanation

@larryellison531 2 года назад

explanation is good.

@jitendertehlan1384 4 года назад

Sir,what's the time complexity for finding height of balanced binary search tree

@PhyleyCS 4 года назад

Using the algorithm described in this video, the time complexity is O(n) (as mention at the end). This is the same no matter what the shape of the binary tree is. Therefore, the time complexity for a balanced binary search tree is still O(n).

@jitendertehlan1384 4 года назад

@@PhyleyCS ok sir,thankyou very much

@dsclips900 Год назад

Hi man, why you stopped uploading videos, they are very instructive, thanks!

@PhyleyCS Год назад

Hello! I got busy with other things and other channels... 🙂 Thanks for asking!

@dsclips900 Год назад

@@PhyleyCS Which channels?

@PhyleyCS Год назад

Mostly related to web development. Recently, I started this channel: www.youtube.com/@StrangestCode

@Brandon-oo1qi 5 лет назад

This is incorrect. Had the left side been the longest path from root to a leaf node then the height would have been 2 not 1. That -1 nonsense is just that. The height of a leaf node is always 0 not -1.

@PhyleyCS 5 лет назад

Yes, it is 2 if we consider the original tree, but since we're considering the *subtree* with root node (2), the height of that *subtree* is 1, not 2.