Find height of a binary tree

[@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 😅

[@xVermyy]

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

[@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 🤞

[@on_a_grind_rn]

How are you guys doing man i hope you're doing fine :) . Just curious to know were you guys able to land a job?

[@WebgaraCom]

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

[@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...

[@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

[@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!

[@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.

[@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 ..

[@lravikiran88]

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

[@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.

[@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..

[@arnabthakuria2243]

You are a great teacher

[@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.

[@jm.101]

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

[@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!

[@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.

[@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

[@vasachisenjubean5944]

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

[@hatsuharu333]

You explain the concepts really well. Thank you!

[@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

[@yangliu8096]

Your video is very enlightening, thank you

[@abuzaid4342]

this man was a genius

[@roushanraj2155]

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

[@leontube007]

max is used by #include

[@usama57926]

amazing explanation i think u are a tutor

[@arbg2566]

Thanks for this course!

[@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 :(

[@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.

[@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?

[@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; } }

[@nick_kosi]

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

[@kanishknagar2606]

great work dude

[@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.

[@siddharthtrikha2051]

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

[@nestorguemez4846]

excellent video!

[@saisanthosh4653]

Very neatly explained. Thank you

[@kevin-kuei]

Brilliant videos!

[@CravinMacNCheese]

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

[@santoshr4212]

this is awesome sir

[@arunkumar-ic5rj]

Very nice explain .Please keep going ....

[@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

[@gmaniket]

Thank you.

[@samruddhipatil1812]

Thanks

[@rainaw0924]

Thank you for the video and a clear explanation.

[@ShivamKendre-fc3su]

Great videos

[@elijaheinstein160]

Good one ! Thanks !

[@Mr1dent1ty]

Really great tutorials!!! Keep it up!!

[@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

[@AdarshTrivedi720]

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

[@deeproy7292]

very well explained...thank you

[@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); } }

[@sushantagawane8683]

Thanks mann !

[@sr5726]

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

[@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?

[@inclinedscorpio]

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

[@gurramsaikiran9383]

U just nailed it :) :) Thanks

[@fsl4faisal]

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

[@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..

[@JonWexlerYT]

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

[@elisson357]

Thanks for sharing this.

[@ashu3707]

thanks a lot

[@kafychannel]

thank you man

[@thuanbuibach7284]

Thank you so much, you are great teacher ^^

[@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.

[@mulgamarathikudipunjabi]

Properly Explained !!

[@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

[@gabrielpereiramendes3463]

Very Good!

[@blearchive]

this 's great tutorial

[@jinyi0313]

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

[@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.

[@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.

[@jr.shivendra4271]

it was brilliant...

[@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

[@alifdoll6372]

Awesome

[@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.

[@alanliang9538]

nice vid ma man

[@sandeepkumaradvocate4035]

Thanks sir

[@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

[@Fauji_Baba]

thanx mycodeschool u r like god to me ..

[@vu5700]

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

[@usama57926]

thank u brother

[@dustbunnys]

Will this technique work for an AVL tree?

[@amandeepsaxena9579]

yes exactly same code will work for AVL trees also

[@roushanraj2155]

for count

[@Luna-fu7ix]

thank ya a lot

[@divyachowdhary2574]

awesome

[@prashantgupta808]

how max function is working here without any definition?

[@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/

[@nedadra1]

really helpfull thank u .

[@manishbisht7740]

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

[@sensen9235]

can you use a static variable?

[@PauloItaliano]

what is actually a difference between the edge and the leaf???

[@memegineer1983]

A leaf node will have no left and right children nodes. 4, 8, 9, 6, 7 are leaf nodes in mycodeschool's example because they do not have a left or right child. Unlike 5, which has a left and right child; 8 & 9 and therefore, not a leaf. An edge is the arrow mycodeschool draws between each node. For example, the root node, 1, has two edges that point to the left child, 2, and to the right child, 3.

[@mayanksrivastava4452]

edge is the line between any two nodes and leaf is the node which has no children.

[@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 .

[@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.

[@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)); }

[@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!

[@1314520Joanna]

height of a tree and height of node three confuses me, but still nice video

[@usama57926]

amazing algorithm

[@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.