0

what is the right way of calculating the height of a BST?

  • the depth of the tree + 1?
  • the number of edges?
  • other?
OrenIshShalom
  • 5,974
  • 9
  • 37
  • 87
Mohamed Mostafa
  • 11
  • 5
  • "The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero." - Wikipedia See https://stackoverflow.com/a/2597754/4181011 – Simon Kraemer Aug 06 '20 at 06:14
  • 2
    You could define height in slightly different ways. It shouldn't really matter though. – eesiraed Aug 06 '20 at 06:15
  • @SimonKraemer - This is an arbitrary definition. If OP stumbles upon an implementation using a different one, this can be misleading. – Benny K Aug 06 '20 at 07:10
  • @BennyK The definition is not arbitrary at all. The height of a binary tree is `the number of edges on the longest path` or `the number of nodes on the longest path -1` or `the depth of the tree -1` --> which are all the same. – Simon Kraemer Aug 06 '20 at 07:45
  • @BennyK I would be surprised if you can find a different definition, but please proof me wrong. Honestly, I would be interested to see if I misinterpreted something. – Simon Kraemer Aug 06 '20 at 07:46
  • @SimonKraemer If I were to implement a tree structure, I could just as easily decide that the height is the number of rows, which means that a tree with a single (root) node is of height 1. The **choice** to address this question in terms of path length **is** arbitrary. – Benny K Aug 06 '20 at 07:49
  • There must be a better forum out there for non programming basic questions like this – OrenIshShalom Aug 06 '20 at 07:52
  • @BennyK For me that's like saying "If I define a new container it is up to me to define the size to not include the first element". You could do that but you would deviate from the majority of definitions. – Simon Kraemer Aug 07 '20 at 06:11
  • Does this answer your question? [How to find Size & Height for a tree?](https://stackoverflow.com/questions/29591015/how-to-find-size-height-for-a-tree) – Simon Kraemer Aug 07 '20 at 06:12
  • Does this answer your question? [What is the definition for the height of a tree?](https://stackoverflow.com/questions/2209777/what-is-the-definition-for-the-height-of-a-tree) – Simon Kraemer Aug 07 '20 at 06:13
  • Does this answer your question? [Confused - Height of Binary tree](https://stackoverflow.com/questions/17449845/confused-height-of-binary-tree) – Simon Kraemer Aug 07 '20 at 06:13
  • Does this answer your question? [What is the difference between tree depth and height?](https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height) – Simon Kraemer Aug 07 '20 at 06:14

0 Answers0