0
$\begingroup$

Does the following 2-3-4 tree have a height of 3 or 2?

2-3-4 tree

If I count from the external nodes i.e. 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 should be 2.

Any clarification on this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Citing from the Wikipedia article on B-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 the answer to the post what is the difference between tree depth and height?, the height of your tree is 2.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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