Minimum and maximum height of binary search trees, 2-3-4 trees and B trees.

Question

Hi, Can anyone please tell me how you find the min/max height of B trees, 2-3-4 trees and binary search trees?

Thanks.

PS: This is not homework.

Answer 1

If you want to know the length of the longest branch you have to traverse the whole tree keeping note of "the longest branch so far".

Answer 2

1. Start from root node and look for its children

2. if it is having a child node then Select the left most child and store others in any one data structure
   else
   if the height of that node is maximum til now
   set it as max
   end if end if

3. Loop through all nodes of tree and whatever you get at last is the maximum height

Similar you can do for minimum

Answer 3

Minimal height of a binary tree is O(log n), maximal is O(n), depending on how balanced it is.
Wikipedia has a lovely bit about B Tree Heights.
I'm not familiar with 2-3-4 trees, but according to wikipedia they have similar isometry to red-black and B trees, so the above link should educate you on that as well.

Answer 4

As for B trees, the min/max heights depend on the branching factor chosen for the implementation.