GATE CSE 1988 | Question: 7i

Question

Define the height of a binary tree or subtree and also define a height-balanced (AVL) tree.

Answer 1

Height of a binary tree is the longest path from it’s root to any of its leaves.

With number of nodes as n,

Max height possible: n-1 (skewed binary trees)

Min height  possible: $floor(\log_{2}n)$ (perfect binary trees)

 

An AVL tree is a height-balanced binary tree where the difference between the heights of the left subtree and the right subtree cannot exceed 1 for all nodes.

Comments

Height of a binary tree is the longest path from it’s root to any of its leaves.
 

It’s not any of the leaves but it is deepest leave. 

An AVL tree is a height-balanced binary tree where the difference between the heights of the left subtree and the right subtree cannot exceed 1 for all nodes.

 It’s not the height but it is difference between number the levels of right subtree and left subtree that has to maintain the balance factor as -1,0,1.

---

@ASNR1010 The “longest path” from root to any of the leaves = the deepest leaf path length. Isn’t it?

Answer 2

Height of binary tree is maximum of distance of all leaf nodes from root node