Geek Answers Handbook

Confused - Binary Tree Height

I am somewhat confused between the logic of calculating the height of a binary tree.

Code 1

public static int findHeight(Tree node) { if(node == null) return 0; else { return 1+Math.max(findHeight(node.left), findHeight(node.right)); } }

Code 2

 public static int findHeight(Tree node) { if(node == null) return -1; else { return 1+Math.max(findHeight(node.left), findHeight(node.right)); } }

I think the second one is correct as it gives the correct answer for the code below: -

 Tree t4 = new Tree(4); Tree t2 = new Tree(2); Tree t1 = new Tree(1); Tree t3 = new Tree(3); Tree t5 = new Tree(5); t4.left = t2; t4.right = t5; t2.left = t1; t2.right = t3; // Prints "Height : 2" for Code 2 // Prints "Height : 3" for Code 1 System.out.println("Height : " + findHeight(t4));

I am confused because many other SO answers show the logic for calculating height by code 1

Conflicting logic

  • Search for heights in the binary search tree
  • Binary tree height

UPDATE:

All, I have a basic doubt about what is the height of the tree?

1. Is this the node between the root and the deepest node of the tree (including both the root and the deepest node)?

2. Isn't this an edge between the root and the deepest node of the tree?

OR

3. It is only about the realization of each person. Are both approaches correct?

+7
java algorithm data-structures binary-tree tree
source share
3 answers

All the difference is that an empty tree has a height of -1 or 0.

According to Wikipedia :

The height of the node is the length of the longest descending path to the sheet from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).

and

The root node has zero depth, the height of the leaf nodes is zero, and the tree with a single node (therefore, with both the root and the leaf) has a depth and height of zero. Usually an empty tree (a tree without nodes, if allowed) has a depth and height of -1.

So, you may be right - the second agrees with this.

Of course, these are all definitions - I would not be too surprised to see a definition consistent with the first version.

+6
source share

Your example has a height of 3 (t4 is the root, t4.left is t2, t2.left is t1) if your understanding of height (1 root of a node has a height of 1, a root of a node with a child or two has a height of 2, etc.)

 t4.left = t2; t4.right = t5; t2.left = t1; t2.right = t3;

So, code 1 is right :))

0
source share

Code 0 will count the root as height 1 (the root must be 0). This means that all subsequent trees will be too large.

0
source share

More articles:


All Articles