Find height of a binary tree

See complete series on data structures here:
• Data structures
In this lesson, we have written code to find height of a binary tree using a simple recursion.
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool

[@madhav3444]

Can't belive these 6years old videos are so much self explanatory and powerful, thanxx mann, you left ds and algo legacy for us

[@Kimoskxt]

Factz

[@mohdsarim4671]

yupp thats a very well explanation

[@bro......]

9 years 😅

[@mayank_upadhyay_19]

Recursion feels like, I am looking in a mirror at myself, who is already looking in his mirror at himself.

[@davidlaidbiggestfan212]

facts

[@pokerfaced8139]

i am a simple man when i see recursion, i panic

[@samkitjain2136]

so true feels like a never ending loop

[@usmanGTA]

Yeah, but each look at yourself slightly differs... With each look, you lose hair. And right before you get to the break case, you die, your life flashes before your eyes as the recursion begins to reverse and return to all of the stacks above it...

[@sparshbohra4135]

source code for people confused: int height (struct bstnode *root) { if (root == NULL) { return -1; } else { int left = height (root->left); int right = height (root->right); int height = (left < right) ? right+1 : left+1; return height; } }

[@abuhurrara9171]

Thanks

[@avinashmaurya3625]

or you can #include in c++ to make max() function work

[@gool7947]

@@bgmishortmoments No it is correct, it should be -1 only because we know height of leaf node is zero but if we take return 0, then it will give height 1 after adding maximum value with 1 (0+1)so it should be -1 only(-1+1) which will ultimately give the height of leaf node zero.

[@siddheshchunale1524]

aah haa me too used bstnode 🤞

[@xVermyy]

Your videos helped me understand in 10 minutes what my data structures professor couldn't help me understand in a semester. Thank you :)

[@WebgaraCom]

You are here in data structure. You save us in final exam. Please keep going!

[@mcirami]

Thank you so much for the videos. I've learned a lot from you. One thing I don't understand about this is how the actual value of the height is found? How is it returning a count of left edges and right to determine which is max?

[@mycodeschool]

Matteo C You need to watch previous videos in this series to understand how recursion works for trees. Find min and max element in a binary search tree

[@11m0]

+mycodeschool I watched the video and I still don't get it. How does it count the number of nodes or the number of edges in the left and right subtrees? Is this something that happens in the background?

[@cph82612]

+11m0 To calculate the height, you only need to find the path to leaf with maximum number of edges. So you make recursive call to go through the tree, and each time the recursive call returns, the value will be incremented by 1. Say when we're on node 5 in the video, it'll first call FindHeight(root -> left), which goes to node 8. Node 8 will again call FindHeight(root -> left). The left child of node 8 is NULL, so it'll return -1. Node 8 then call FindHeight(root -> right). The right child of node 8 is also NULL, so it'll return -1. Now node 8 will return max(left height, right height) + 1. Since both child nodes of node 8 are NULL and return -1 (max(-1,-1) = -1) , it'll return -1 +1 which is 0. It shows the height of node 8 is 0. Now node 5 calls FindHeight(root -> right), which goes to node 9, and like node 8, it'll return 0 because the height of 9 is 0. And then node 5 returns max(left height, right height) + 1, which will be max(0,0) + 1 = 1. When node 5 return height to node 2 with height of 1, node 2 returns again max(left height, right height) + 1, which will be max(0, 1) + 1 = 1+1 = 2 (left height is height of node 4 which is 0), so height of node 2 will be 2. Because each recursive call returns (something) + 1, and the (something) compares the left and the right height, the maximum height can be determined and incremented in each return.

+Benjamin Hsu thank you ı really understand.

[@lravikiran88]

superb sir.... u just made the explanations much more clearer...... and we must all appreciate the way our sir in video used recursion to compute the height ... wow talk about arithmetics on recursion ..

[@easynow6599]

excellent video! especially the fact that for the base case (return -1) you showed how it will work for a leaf node.. here is the Python code: def height(root): if not root: return -1 heightRight = height(root.right) heightLeft = height(root.left) return max(heightRight, heightLeft) + 1

[@codysiegmann5637]

Awesome explanation of the recursive calls as well as the base case (exit condition) and how changing -1 and 0 in the base case will calculate the height of the tree or the number of nodes in the tree, respectively.

[@VarunVishwakarma1]

Why did u stop making videos? Please continue. You are the one who made DS easy for me.

[@vikramsapate8703]

He died in one car accident.

[@qR7pK9sJ2t]

if you know the logic of height and depth.. Directly go to 3:05

[@mohammedsadiq1567]

Thank you!

[@krishnasai573]

Is it BINARY TREE or BINARY SEARCH TREE..... There is a lot of difference between those two Binary tree :-Tree where each node has up to two leaves 1 / \ 2 3 Binary search tree :-Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent. Hope that this is helpful to anybody :)

[@lravikiran88]

it is bst

[@InfamousBlackGuy]

Wouldn't change the process of finding the height of the tree.

[@chandramohanrai9314]

your videos are amazing..... a student can learn starting from 0 to 90% of data structure in just 3-4 days. can u share link for source code of height of b.s.t.

[@jm.101]

Such a great explanation! Helped me to understand balanced and unbalanced trees!

[@vijaykari1809]

As we use in general terms, height - measured from bottom to top(i.e.,)from ground level to how much height it went depth - measured from top to bottom (i.e.,) from ground level to how deep it went..

[@khursheedali8286]

we can also do inorder or any traversal and at each node increment count .... now use the formula ceiling( log(n+1) - 1 ) for finding height ... n- nno of nodes

[@arnabthakuria2243]

You are a great teacher

[@tringuyenucminh167]

oh god, you are a good teacher. Easy to understand.

[@VISHALBHANDARE]

int maxDepth(struct node* node) { if (node==NULL) return -1; else { /* compute the depth of each subtree */ int lDepth = maxDepth(node->left); int rDepth = maxDepth(node->right); /* use the larger one */ if (lDepth > rDepth) return(lDepth+1); else return(rDepth+1); } } #functionInC

[@monicaslv323]

+VISHAL BHANDARE Thank you very much. I am so confused about trees. I dont know how i call its recursive functions from main in ADT.

[@hatsuharu333]

You explain the concepts really well. Thank you!

[@Name-pn5rf]

can we do the if statement as if(node.left==null && node.right==null){ return 0; } I did it and it gave me errors...why did this happen?

[@shivamkumarchauhan9648]

when node is null itself then how it will get value of node->left and node->right?

[@lravikiran88]

sir your logic on how u use recursion for finding the sum is superb.....

[@nick_kosi]

Thank YOU Very Much for the clarity God bless YOU!!!!!!!!!!!

[@yangliu8096]

Your video is very enlightening, thank you

[@2222stunner]

Its worth pointing out that when 'max' is defined as a macro, the tree is traversed in a different order as compared to a function based one. Specifically, in the function based one, a node is visited atmost once. But in macro based one, some nodes are visited many times (verified it by using printf). The results are the same, however. Can someone please explain why it is so?

[@ashwanivarshney9406]

sir all the videos were very helpful but can you please provide some more videos related to algorithms like red black tree,greedy algorithms graph dfs and bfs and all...

[@sarvdeepsangwan1207]

one of the partners of mycodeschool died in an accident. so other one decided to not post videos anymore :(

[@navroze92]

Could you please upload videos in dynamic programming it is one of the most powerful and fundamental concepts in computer science if you could do that it would be of great help as there is no one who teaches computer science concepts like you do:)

[@jaekim9496]

navroze92 Hey! I don't know if you still want to learn about dynamic memory, but he has a series of videos on it if you want to watch it. They are very very very good.

[@navroze92]

Jae Kim Could u please put the link for dynamic programming

[@rashmih8774]

somebody reply please dont we have to make a count here !! like we have to increment the count each time we parse right !

[@KrishnaKr]

Rashmi H Thats the beauty of recursion...You need to see previous lectures on binary trees... :)

[@VikasYadav-vy4wd]

the addition is taking place in this line of code "return max(FindHeight(root->left), FindHeight(root->right)) + 1;" The +1 is always performed after the function is finished being called. We find the lowest depth of the tree and then we break the recursive search for the bottom with (root == null), and we send -1 + 1 = 0 which goes back up and becomes 0+1= 1 which goes back up and becomes 1+1 = 2 which goes up and so on and so on... until we close all the recursive calls.

[@GamersCreedTeam]

Thanks!

[@souravraj9505]

@@VikasYadav-vy4wd plz explain the counting more clearly...

[@Aman-vd3tr]

@@souravraj9505 every time function is used(recursion function) it increments its value by 1

[@roushanraj2155]

Rashmi ,you have to store base condition of each recursion of node

[@sr5726]

Amazing Videos! Could you please tell, what software you are using to capture and make these videos?

[@emanuelebosco594]

thanks a lot for helping us!

[@watchit186]

sir ..nicely done...but one thing i didn't get...nowhere count is incremented.. last leaf node returning -1 to its parent node..but wat its parent node returning to its parent node..its totally confusing..can u explain bit more on this..

[@JonathanWexlerConnect]

ravi kumar In the actual code, he returns Max of two options (left node and right node), and adds 1 to whichever is bigger. That in turn returns to whichever node before that called the recursive function, and that call will also add 1. This continues for each node in the tree until it reaches the root node, which will add 1 to the final result, and return that Integer value to whoever called the function originally. In other words: null leaf returns -1, the node before takes the -1 and adds 1 (=0), the node before that takes the 0 and adds 1 (+1).....(nDepth-1)

[@AhmedMahmoud-qu6nq]

Jonathan Wexler so please can you explain how the stack works with the line return max (findheight(root->left),findheight(root-.right)); mycodeschool

[@vasachisenjubean5944]

int height(TreeNode root) { if(root==null) { return -1; } return Math.max(1+height(root.l), 1+height(root.r)); }

[@gowtham3340]

Your voice is perfect. No need subtitles... You just avoid the subtitles , because some of the content not visible

[@shivamsaxena5854]

you can turn off caption by clicking on the 3 vertical dots showing on the upper right side of your screen

[@lynx2244]

Why don't you turn off the captions then? There might be some students who are deaf or audibly impaired!

[@joyawang5952]

Anyone has the same problem with me? The function only returns the result of FindHeight that goes last in the max function parameters. For example, if I put "return max(FindHeight(root->left), FindHeight(root->right)) + 1;" , it returns the height of right, and if I switch left and right like this, "return max(FindHeight(root->right), FindHeight(root->left)) + 1;" , it returns the height of left.

[@arbg2566]

Thanks for this course!

[@CravinMacNCheese]

this helped so much. do you have a video on balancing a binary tree?

[@saisanthosh4653]

Very neatly explained. Thank you

[@ES11777]

0:54 small mistake: you said that the number 3 is a leaf node but it's not.

[@elusk4545]

At 1:17, you state the height of the tree is 3... Is root not considered part of the tree?

[@dustbunnys]

Eric Lusk, you can think about it as number of nodes -1 if you want to include the root as part of the tree.

[@leontube007]

max is used by #include

[@ziddy26]

how come the height of node 2 is 2?by your definition of height, isn't it is supposed to be 1. If it is 2, then the height of the tree should be 4.

[@mehedihasanhridoy1701]

yeah i also don't get it

[@siddharthtrikha2051]

Thanks a lot for all your videos :) Keep up the good work.

[@rainaw0924]

Thank you for the video and a clear explanation.

[@usama57926]

amazing explanation i think u are a tutor

[@kayjay1278]

can it work for binary search tree also? I mean do we need to make any changes if we want to make this code work for binary search tree instead of binary tree?

[@mycodeschool]

Binary search tree is only a special kind of binary tree. So, yes , this will work for a binary search tree without any change.

[@T4l0nITA]

really great video, i was wondering, is there a way to implement this function with an iterative algorithm ?

[@mycodeschool]

T4l0nITA It won't be so intuitive, but yes, any recursion can be implemented using iteration.

[@aryanverma7800]

@@mycodeschool Are you in hell or heaven right now??

[@ramviswanadhapalli4397]

​@@aryanverma7800why the fuck would you ask that brooo

[@vangjelgramozi324]

And how do you build the max function? Instead of max(a,b) do you write return ( FindHeight(root->left) > (FindHeight(root->right) ? FindHeight(root->left) : FindHeight(root->right) ); Is this correct or no?

[@prasanna5836]

Here 'FindHeight' function returns an integer,it's like writing return some_int_1 > some_int_2 ? some_int_1 : some_int_2; which is correct.

[@Mr1dent1ty]

Really great tutorials!!! Keep it up!!

[@fsl4faisal]

neat explanation..!! Thank you so much..!

[@deeproy7292]

very well explained...thank you

[@shailjakantupadhyay5183]

+mycodeschool I watched the all your previous videos and understood it but specifically this video i don't get. How does it count the number of nodes or the number of edges in the left and right subtrees? i need more explanation of code with any example.

[@thuanbuibach7284]

Thank you so much, you are great teacher ^^

[@biochem7092]

if (root is Null) it should return 0. Because it means, that the upper level node will take it as 0. Code runs line by line, and when it returns, the function is finished, so it won't add +1 to 0. It is fine, that when root is Null, return 0. Please watch other videos and learn from their lectures. I do not agree that you are returning -1 for this function.

[@earthwombat]

i think you were confused by the recursion and which node is which. It will not return at ```if (root == null)``` for node 7 because it is not null, but the leaves are.

[@santoshr4212]

this is awesome sir

[@gurramsaikiran9383]

U just nailed it :) :) Thanks

[@kevin-kuei]

Brilliant videos!

[@letmeregisterbitch]

Great lesson! Thanks alot

[@gmaniket]

Thank you.

[@elijaheinstein160]

Good one ! Thanks !

[@ShivamKendre-fc3su]

Great videos

[@AdarshTrivedi720]

Great explaination.................bang on.....

[@arunkumar-ic5rj]

Very nice explain .Please keep going ....

[@hhcdghjjgsdrt235]

int MaxDepth(TreeNode root) { if (root == null) return 0; int HOL = MaxDepth(root.left); int HOR = MaxDepth(root.right); if (HOL >= HOR) { return HOL + 1; } else { return HOR + 1; } }

[@samruddhipatil1812]

Thanks

[@kanishknagar2606]

great work dude

[@jinyi0313]

how to find possible triangle in binary tree. example if i insert 7 it will return 4 triangle. thank you for answer

[@nestorguemez4846]

excellent video!

[@vu5700]

Whats the output of max function if left is equal to right

[@ashu3707]

thanks a lot

[@monicaslv323]

int findheight(struct nodo *root)...how do you call this kind of function from main()??

[@11m0]

+M. Santos it will look similar to this public static void main(String[] args) { BinaryTree tree = new BinaryTree(); //This is based on the name of your class tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); System.out.println("Height of tree is : " + tree.maxDepth(root)); }

[@abuzaid4342]

this man was a genius

[@blearchive]

this 's great tutorial

[@mulgamarathikudipunjabi]

Properly Explained !!

[@sushantagawane8683]

Thanks mann !

[@inclinedscorpio]

*Return 0 not -1 because the number is returned to parent of leaf node and not the leaf node !!*

[@siddharthmagadum16]

what about the root node being null? the height would be -1? or still 0? . According to the code it is -1 , but I'm doubting on it ...

[@siddharthmagadum16]

@@bgmishortmoments Hmm, now I would think that just returning -1 is correct as there will be no tree at all if root is null. And Answer would be 0 in case of only 1 node(root).

[@bgmishortmoments]

@@siddharthmagadum16 yah I too realized now

[@shohanurrahman9965]

///find height of a binary tree int FindHeight(BstNode* node) { if (node == NULL) return 0; else { /* compute the depth of each subtree */ int lheight = FindHeight(node->left); int rheight = FindHeight(node->right); /* use the larger one */ if (lheight > rheight) return(lheight + 1); else return(rheight + 1); } }

[@kafychannel]

thank you man

[@jaykaushik9516]

Please ellaborate more for finding height of tree

[@sgg2037]

Hi, do you have a lesson on finding Floor and Ceil from a Binary Search Tree? Thanks.

[@shyam5631]

he is dead.

[@SWAPNILMISHRABLC]

@@shyam5631 no he is not. His friend died and not him

[@dustbunnys]

Will this technique work for an AVL tree?

[@amandeepsaxena9579]

yes exactly same code will work for AVL trees also

[@prashantgupta808]

how max function is working here without any definition?

[@abinavdepp]

very nice tutorials. i have a question!. here in this video where do you find the height of the left tree and right. it just returns -1 if root is null na?

[@mycodeschool]

abinav depp Please watch previous videos in data structures series to understand how recursion works for tree. You will be able to understand how this is working. Introduction to data structures

[@gabrielpereiramendes3463]

Very Good!

[@Luna-fu7ix]

thank ya a lot

[@yustinayasin5539]

Hi guys! i've tried this pseudocode in C and the result is "Error: Tree is empty" appear everytime the recursion called. The error shouldn't appear because my tree isn't empty. Can anyone explain my error please? Thank you

[@yustinayasin5539]

@Yash Dave i already resolve the problem. Thank you for intending to help!

[@Fauji_Baba]

thanx mycodeschool u r like god to me ..

[@sandeepkumaradvocate4035]

Thanks sir

[@jr.shivendra4271]

it was brilliant...

[@vladyslavmiachkov7431]

But if tree wiill be huge that cause stack overflow of recursion doesnt; it?

[@obinnaubah9045]

Yes. That's why there is a more efficient algorithm. www.afternerd.com/blog/python-check-tree-balanced/

[@sensen9235]

can you use a static variable?

[@usama57926]

thank u brother

[@nguaial8490]

I don't see how this function can return values other than 0 since the only numerical value that is returned is -1. please help me to understand.

[@lravikiran88]

eg: when u reach leaf node , the function checks its address and it is not null so it will do a recursion all using its left and right addresses but which are null. so when calls are made for both of them ,since addresses of both show null it would return a -1 as in program . so the call will go back to leaf node function and max (-1,-1)+1=-1+1=0 is returned as op. later when we go forward for every recursion call +1 is added uptil root.. that is how it works. i hope i am of some help to u

[@sadeqsadeq7128]

+ravi kiran thanks

[@lravikiran88]

Sadeq Sadeq anytime bro

[@sergiojimenez3445]

anyone could explain me why is O(n) if this is supossed to check all the branches

[@miljan9602]

Dude, you gave yourself a answer. If it needs to check every branch then it is O(n), n is number of branches and it checked every branch once.

[@streamcoders3552]

Recursion is like, you are dreaming during sleep and inside dream you are also dreaming, then again inside that dream you are sleeping and dreaming. It's like inception movie :D .

[@nedadra1]

really helpfull thank u .

[@bipul2138]

awesome

[@manishbisht7740]

Can anyone tell me how to find height of a tree represented as adjacency list? BTW great video.

[@vijaykari1809]

Hi Sir..Thanks a lot for your videos and in helping me to come out of fear from concept of non-linear DS ..I am not only able to understand these concepts for the first time, but also getting more interest in learning about the concepts. I HAVE A SUGGESTION. Can we logically represent the arrow marks of HEIGHT as edges starting from leaf node to the destination(be it node at any level/root node) & DEPTH with edges(arrow mark) starting from root node to that destination(be it node at any level/leaf node).. This can be a better pictorial representation for clear understanding, to newbies like me. Thanks & correct me if i am wrong.

[@alanliang9538]

nice vid ma man