Calculating the height of a binary tree

Question

I need help with the theory on calculating the height of a binary tree, typically the notation.

I have read the following article:

Calculating height of a binary tree

And one of the posts gives the following notation:

height(node) = max(height(node.L), height(node.R)) + 1

Let's assume I have the following binary tree:

     10
   /   \  
  5    30
 / \   /  \ 
4  8  28  42

Do I therefore calculate the max value on the left node (8) and the max node on the right (42) and then add 1? I don't quite understand how this notation works in order to calculate the height of the tree.

Answer 1

Recursive approach for height of binary tree as below in user defined binary tree in Java-

class Node
{
    int data;
    Node left, right;
    public Node(int item)
    {
        data = item;
        left = right = null;
    }

    boolean isLeaf() { return left == null ? right == null : false; }
}

public class BinaryTree {
    Node root;
    public BinaryTree() {
        root = null;
    }
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root= new Node(1);
        tree.root.left= new Node(2);
        tree.root.right= new Node(3);
        tree.root.left.left= new Node(4);
        tree.root.left.right= new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.left = new Node(8);
        tree.root.right.left.right = new Node(9);
        System.out.println("\n Height of tree is : "+tree.height(tree.root)); 
    }

    /*Height of Binary tree*/
  public int height(Node root) {
        if (root == null)
            return 0;
        else {
            int lHeight = height(root.left);
            int rHeight = height(root.right);

            if (lHeight > rHeight)
                return (lHeight + 1);
            else return (rHeight + 1);
        }
    }
}

With the above code you can easily create binary tree without using library in java.

Answer 2

You can use the recursive approach.

int height(Node root) {
   return root==null ? 0 : Math.max(height(root.left), height(root.right)) +1;
}

Answer 3

I'll try to explain how this recursive algorithm works:

height(10) = max(height(5), height(30)) + 1

height(30) = max(height(28), height(42)) + 1
height(42) = 0 (no children)
height(28) = 0 (no children)

height(5) =  max(height(4), height(8)) + 1
height(4) = 0 (no children)
height(8) = 0 (no children)

So if you want to calculate height(10), you have to expand the recursion down, and than substitute results backwards.

height(5)  = max(0, 0) + 1
height(30) = max(0, 0) + 1
height(10) = max(1, 1) + 1
height(10) = 2

EDIT:

As noted in comments:
height of binary tree = number of layers - 1
Therefore there should be assumption that height of empty node is equal to -1 i.e:

height(empty) = -1 

or

height(null) = -1 

this way

height(42) = max(height(null), height(null)) + 1
height(42) = max(-1, -1) + 1
height(42) = -1 + 1
height(42) = 0

I have corrected calculation above.

Answer 4

Repeated Question

Despite being good introductions to recursion, I'm a bit surprised by all the incorrect answers as to the height of a binary tree, so I thought I'd offer the correct solution. I did some digging and this question is answered properly here: https://stackoverflow.com/a/2597754/5567854.

Reference

According to Wikipedia, "A tree consisting of only a root node has a height of 0", not 1 as the other answers state. Therefore, with the example from the question:

     10
   /   \  
  5    30
 / \   /  \ 
4  8  28  42

If 10 was the root node to find the height of that tree, then the height is 2, not 3.

Correct Code

This solution is one of many possible solutions in C Language...

size_t binary_tree_height(const binary_tree_t *tree)
{
    size_t r, l, height = 0;

    if (tree)
    {
        r = tree->right ? binary_tree_height(tree->right) + 1 : 0;
        l = tree->left ? binary_tree_height(tree->left) + 1 : 0;
        height += (r > l ? r : l);
    }
    return (height);
}

Answer 5

#include<stdio.h>
#include<stdlib.h>


/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
struct node 
{
    int data;
    struct node* left;
    struct node* right;
};

/* Compute the "maxDepth" of a tree -- the number of 
    nodes along the longest path from the root node 
    down to the farthest leaf node.*/
int maxDepth(struct node* node) 
{
   if (node==NULL) 
       return 0;
   else
   {
       /* compute the depth of each subtree */
       int lDepth = maxDepth(node->left);
       int rDepth = maxDepth(node->right);

       /* use the larger one */
       if (lDepth > rDepth) 
           return(lDepth+1);
       else return(rDepth+1);
   }
} 

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data) 
{
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

int main()
{
    struct node *root = newNode(1);

    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5); 

    printf("Hight of tree is %d", maxDepth(root));

    getchar();
    return 0;
}

Answer 6

C enthousiasts, feel free to have a read at this article:

http://www.csegeek.com/csegeek/view/tutorials/algorithms/trees/tree_part3.php

I re-aranged the C code to PHP:

function getTreeHeight($node) {
    if (!isset($node['left']) && !isset($node['right'])) {
        return 0;
    }

    $leftHeight  = getTreeHeight($node['left']);
    $rightHeight = getTreeHeight($node['right']);

    if ($leftHeight > $rightHeight) {
        return $leftHeight + 1;
    } else {
        return $rightHeight + 1;
    }
}

$array = array(
    'value' => 5,
    'left' => array(
        'value' => 2,
        'left' => array(
            'value' => 1,
        ),
        'right' => array(
            'value' => 4
        ),
    ),
    'right' => array(
        'value' => 11,
        'left' => array(
            'value' => 7
        ),
        'right' => array(
            'value' => 23,
            'left' => array(
                'value' => 16
            ),
            'right' => array(
                'value' => 34
            ),
        ),
    )
);

echo getTreeHeight($array); //output 3

Answer 7

The highest number of nodes that is possible in a way starting from the first node (ROOT) to a leaf node is called the height of tree. The formula for finding the height of a tree h=i(max)+1 , where h is the height and I is the max level of the tree

Answer 8

Find out the root node, then look for the longest path that u can cover(means the maximum number of node you can cover in that path), if u get that path, then check how many branches or edges you have covered, the total number of branches you have covered is the height of the tree

Answer 9

Do u know the definition of node's height? I would answer it as the farthest distance to a reachable leaf(so all leaf have height 0)...now try to find the height of every node from bottom to top..that would your algo..

Answer 10

Height of the tree is the length of the path from the root to the deepest node in the tree. Here is the shortest algo to do so

int height(Node root){
   if(root == null )
       return 0;
   return 1+max{height(root.left), height(root.right)};
}