Find height of a binary tree 

Factz

yupp thats a very well explanation

9 years 😅

facts

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

so true feels like a never ending loop

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

Thanks

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

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

aah haa me too used bstnode 🤞

Thank you!

He died in one car accident.

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

+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?

+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.

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

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

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.

Jae Kim Could u please put the link for dynamic programming

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

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

+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.

it is bst

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

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

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

​@@aryanverma7800why the fuck would you ask that brooo

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.

+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)); }

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

yes exactly same code will work for AVL trees also

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

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

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.

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

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

he is dead.

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

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

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.

Thanks!

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

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

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)

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

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.

yeah i also don't get it

if you dont understand recursion then just write down all the step on paper then you will definately understand

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

@@siddharthmagadum16 yah I too realized now