CODEWITHSUNDEEP
c++avl-tree
jbusta27
jbusta27

Reputation: 21

Why add 1 when calculating height of AVL tree?

While updating the heights of my subtrees in an AVL rotation implementation, I noticed in the example the code that the height function is

x->height = max(height(x->left), height(x->right)) +1;

Does anyone know where the +1 comes from and why?

Thanks!

Upvotes: 2

Views: 350

Answers (1)

chickennuggies
chickennuggies

Reputation: 63

Without seeing any actual code, I'm assuming max(height(x->left, height(x->right) doesn't include the node you are calling the function on. Height function returns whichever subtree is higher and + 1 for your current node to get the total height.

Upvotes: 5

Related Questions