0
$\begingroup$

Consider the following 2-3-4 tree.
2-3-4 tree
Does this have a height of 3 or 2 ?
If I count from the external nodes ie. the ones with the square boxes then height should be 3.
Not sure if they are to be included in the height as they are represented as NIL.
If they are not to be included then the height of the tree = 2
Any clarification on this.

$\endgroup$
0
$\begingroup$

Citing from Wikipedia (https://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree)

Every node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively.

Thus, since the squares in the bottom row do not hold data elements, they are not nodes of the 2-3-4 tree.

Then, using the definition of height from https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height the height of your tree is 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.