Search code examples
binary-search-tree

Binary Search Tree and height

Hello for our assignment, we were supposed to creat BST with input in following order: Victor, Zebra, Hotel, Alpha, Bravo, Charlie, India, Zebra, Xray

So our program did its thing and got initial image of bst

And then it asked us to remove first India and then Victor from the tree.

And we got Tree after removing two nodes

And then it asked us for the height of alpha bravo and charlie and we said it was alpha - 2, bravo - 1 and charlie - 0

But the answer was alpha - 1, bravo - 0 and charlie - 2

Is our visualization of bst wrong?

Solution

  • Your visualisation is correct.

    You should note that it is more typical to refer to a binary tree as having a height and each node in a binary tree having a certain 'depth' - that is, the root has depth 0 in the tree. In this example, 'Hotel' has depth 0 and 'Charlie' has depth 3. The first tree you posted has an overall height of 4. The second tree has an overall height 3.