Height and Depth of a Binary Tree

This article aims to distinguish between 2 of the properties of binary trees called as height and depth. As per binary tree terminology below are the definitions of height and depth of binary tree.

Height: The height of a binary tree is the number of edges along the longest path from the root node down to the farthest leaf node

Depth: The depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node

Few terminologies of a binary tree

An empty tree has height -1

A tree with only one node (root node) has height 0

Examples

Lets take a look at few binary tree examples to make the difference clear

Let’s count height of Tree 1, Tree 2, Tree 3 and Tree 4

Tree 1: we trace nodes 50–70–60–55, which gives 3 edges between the nodes, hence height as 3

Tree 2: we trace nodes 15–20–25, which gives 2 edges between the nodes, hence height as 2

Tree 3: we trace nodes 14–15–18–21–25–45, which gives 5 edges between the nodes, hence height as 5

Tree 4: we trace nodes 12–14–18–16, which gives 3 edges between the nodes, hence height as 3

Let’s count depth of Tree 1, Tree 2, Tree 3 and Tree 4

Tree 1: we count nodes 50–70–60–55, which gives 4 nodes, hence depth as 4

Tree 2: we trace nodes 15–20–25, which gives 3 nodes, hence depth as 3

Tree 3: we trace nodes 14–15–18–21–25–45, which gives 6 nodes, hence depth as 6

Tree 4: we trace nodes 12–14–18–16, which gives 4 nodes, hence depth as 4

Let’s look at the below code snippet for height and depth of binary tree.’

Assuming we have built the trees from 1 to 4.

public class HeightDepthBST {
 Node root;
 int height (Node node) {
    if (node == null) return 0;
    else if (node.left == null && node.right == null) return 0;
    return 1 + Math.max (height(node.left), height(node.right));
 }
 int depth (Node node) {
    if (node == null) return 0;
    int left = depth (node.left);
    int right = depth (node.right);
    return (left > right) ? left+1 : right+1;
 }
 public static void main(String[] args) {
    HeightDepthBST a = new HeightDepthBST();
    a.root = a.createBST();
    System.out.println("Height "+height(a.root));
    System.out.println("Depth "+depth(a.root));
 }
 Node createBST() { // Tree 4 in above
   root = null;
   root = add (root, 12);
   root = add (root, 6);
   root = add (root, 5);
   root = add (root, 8);
   root = add (root, 7);
   root = add (root, 9);
   root = add (root, 14);
   root = add (root, 18);
   root = add (root, 16);
   return root;
 }
 Node add (Node node, int data) {
   if (null == node) return new Node (data);
   else if (data < node.data) node.left = add (node.left, data);
   else if (data > node.data) node.right = add (node.right, data);
   return node;
 }
}
class Node {
  int data;
  Node left, right;
  Node (int data) {
    this.data=data;
  }
}

Code explanation: To find out height and depth we write concise code with recursion. The height() recursively calls itself with left subtree and right subtree. The condition which distinguishes height from depth is given below : if (node.left == null && node.right == null) return 0. This way we stop adding 1 to height if left leaf and right leaf is null for a given node. We add 1 to height because a tree with only root node has height 0, so once tree advances after this condition we start adding 1 to height. We add 1 to the max value of height from left subtree and right subtree for a given node. We find max of the height from left subtree and right subtree because we need to go to farthest leaf node. The depth() recursively calls itself with left subtree and right subtree and returns 0 when either left subtree or right subtree or both null for a given node. The code is similar to height() except it distinguishes between left subtree and right subtree and base condition checks only for null if (node == null) return 0;

The time complexity of height() and depth() code is O(N).

Conclusion

In this article, we traced 2 of the important properties of a binary tree namely height and depth. We visited the code to calculate them. We also saw what is the difference between them from tree’s perspective.