Calculate Height of any Tree in Java (Non-Binary Tree)

Computing height of a tree in Computer Science is very common. Most of the examples and online discussions talk about computing the height of a Binary Tree.

The example method I am sharing can be used to compute the height of any tree. So even if you have a non-Binary tree, you can use this method to get the tree height.

Since we are talking about a non-Binary tree, a node can have more than 2 children hence we have to declare the children as a list in Node class. Here is my Node class.

class Node<E> {
	int height;
	Node<E> parent;
	List<Node<E>>childern;
}

As you can see we have a field of type Node to reference the parent node, and a list of Nodes to reference the children of this node.

Using this class definition with recursion we can compute the height of a tree (including non-Binary tree).

getTreeHeight:

public int getTreeHeight(Node<Integer> root) {
   int height = 0;
    if (root == null ) {
	return height;
    }
    if (root.childern == null) {
	return 1;
  }

   for (Node<Integer> child : root.childern) {
	height = Math.max(height, getTreeHeight(child));
  }
   return height + 1;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *