Height of Binary Tree

Introduction

The height of a binary tree is a measure of how tall or deep the tree is, representing the maximum length from the top (root) to the bottom (leaf node). It tells us how many levels the tree has and helps us understand its structure and performance.

In simple terms, it's like counting the steps from the top to the bottom of a tree, where each step connects a parent node to its child node. A balanced tree with similar levels is more efficient for operations like searching and insertion, taking fewer steps to find or add elements. On the other hand, an imbalanced tree with uneven levels can make these operations slower as it requires more steps to reach the desired node.

Overview

The height of a binary tree is a fundamental concept that measures the depth or maximum length from the root node to a leaf node in the tree. It represents the number of edges in the longest downward path from the root to a leaf. The height of a binary tree directly affects its performance characteristics and efficiency in various algorithms and data structures.

Ways to Find the Height of a Binary Tree

There are several ways to find the height of a binary tree:

1. Recursive Approach

The most common and straightforward method is to use a recursive function. The recursive approach traverses the tree starting from the root and recursively calculates the height of each subtree. It returns the maximum height between the left and right subtrees plus one for the current node. This method is simple to implement but may lead to stack overflow for very deep trees.

2. Iterative Level Order Traversal

An iterative approach using level order traversal (Breadth-First Search) can also find the height of the binary tree. The idea is to traverse the tree level by level and count the number of levels visited. The last level visited will be the height of the binary tree. This method consumes more memory as it stores all nodes at each level.

3. Bottom-Up Approach (Post-order traversal)

Another approach is the bottom-up method, which uses post-order traversal. Starting from the leaf nodes, it recursively calculates the height of each subtree and returns the height to its parent nodes. This way, the height of the entire binary tree is calculated from the bottom to the top.

4. Morris Traversal

There is a traversal technique called Morris Traversal which is non-recursive and efficient in terms of space. It can also be used to determine the height of a binary tree. However, it is considered more advanced and less commonly used compared to other methods.

Example:

Code:

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int data;
   Node *left;
   Node *right;
};
int findHeight(Node *node) {
   if (node == NULL)
      return 0;
   else {
      int leftHeight = findHeight(node->left);
      int rightHeight = findHeight(node->right);
      if (leftHeight > rightHeight)
         return (leftHeight + 1);
      else
         return (rightHeight + 1);
   }
}
Node *addNode(int data) {
   Node *newNode = new Node();
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;

   return newNode;
}
int main() {
   Node *root = addNode(1);

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

   cout << "The height of binary tree is: " << findHeight(root);
   return 0;
}

Recursive Way

Code:

#include <iostream>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int getHeight(TreeNode* root) {
    if (root == NULL) {
        return -1; // Height of an empty tree is -1
    }

    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);

    return 1 + std::max(leftHeight, rightHeight);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Height of the binary tree: " << getHeight(root) << std::endl;

    return 0;
}

This getHeight function recursively calculates the height of the binary tree by computing the height of the left and right subtrees and then taking the maximum of the two heights. The height of an empty tree is considered to be -1, and the height of a tree with a single node (root) is 0.

Non-Recursive Way

Code:

#include <iostream>
#include <queue>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return -1; 
    }
    std::queue<TreeNode*> q;
    q.push(root);
    int height = -1; 
    while (!q.empty()) {
        int size = q.size();
        height++;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return height;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Height of the binary tree: " << getHeight(root) << std::endl;

    return 0;
}

In this implementation, we use a queue to perform a level-order traversal(also known as breadth-first traversal)l of the binary tree. For each level, we process all nodes in that level and increment the height. This approach does not use recursion and gives you the height of the binary tree.

Find the Maximum Depth or Height of a Tree using Level Order Traversal

Code:

#include <iostream>
#include <queue>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    std::queue<TreeNode*> q;
    q.push(root);
    int depth = 0;

    while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        
        depth++;
    }

    return depth;
}
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Maximum depth of the tree: " << maxDepth(root) << std::endl;

    return 0;
}

In this example, the maxDepth function uses a level-order traversal with a queue to explore each level of the tree. For each level, it increments the depth variable. The final value of depth will represent the maximum depth (height) of the tree. This approach does not use recursion and provides the maximum depth of the tree using level order traversal.

What is a Binary Tree?

A binary tree is a hierarchical data structure in computer science composed of nodes, where each node has at most two children, referred to as the left child and the right child. The topmost node in the tree is called the root, and nodes with no children are known as leaf nodes. Binary trees are extensively used in various algorithms and data structures due to their simple yet powerful nature.

Height of a binary tree: example:

In the above example, we have a binary tree with five nodes, labeled from 1 to 5. The tree starts with the root node labeled 1. The left child of the root is node 2, and the right child is node 3. Node 2, in turn, has two children: node 4 on the left and node 5 on the right. Nodes 4 and 5 are leaf nodes as they have no children.

It's essential to remember the rules that govern binary trees:

1. Each node can have at most two children, which are represented as the left child and the right child.

2. Nodes with no children are leaf nodes.

3. The topmost node without any parent is the root node.

4. The binary tree can be empty, meaning it has no nodes. In this case, it is often referred to as an empty binary tree.

Binary trees can be more complex and larger, with numerous levels and nodes. The depth of a binary tree is the maximum level of any node in the tree, while the height is the length of the longest path from the root to a leaf node, as explained in the previous response. The shape and structure of binary trees can significantly affect their performance and the efficiency of various operations performed on them.

Height of Binary Tree: Formula

The height of a binary tree is calculated as follows:

1. An empty tree (a tree with no nodes) has a height of -1.

2. A tree with a single node (only the root node) has a height of 0.

3. For a tree with multiple nodes, its height is equal to the maximum height of its left and right subtrees, plus 1.

So, if you have a binary tree, you can find its height by checking the height of its left and right subtrees and then taking the maximum of those heights. Finally, add 1 to the maximum value to get the height of the entire tree.

The height of a binary tree measures the length of the longest path from the root to a leaf node, where each step moves from a parent node to its child node. It's an essential metric that impacts the efficiency of various operations on the tree, and it helps us understand the structure and performance characteristics of the binary tree.

Code Implementation

Height of Binary Tree in C++

Code:

#include <iostream>
#include <algorithm> // For std::max

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

int heightOfBinaryTree(TreeNode* root) {
    if (root == nullptr) {
        return -1;
    }
    int leftHeight = heightOfBinaryTree(root->left);
    int rightHeight = heightOfBinaryTree(root->right);
    return 1 + std::max(leftHeight, rightHeight);
}

int main() {
    // Constructing the binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Calculate the height and print it
    int height = heightOfBinaryTree(root);
    std::cout << "Height of the binary tree is: " << height << std::endl;

    // Don't forget to free the memory
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

Height of Binary Tree in C

Code:

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int heightOfBinaryTree(struct TreeNode* root) {
    if (root == NULL) {
        return -1;
    }
    int leftHeight = heightOfBinaryTree(root->left);
    int rightHeight = heightOfBinaryTree(root->right);
    return 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight);
}

int main() {
    // Constructing the binary tree
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->left->val = 4;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->val = 5;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // Calculate the height and print it
    int height = heightOfBinaryTree(root);
    printf("Height of the binary tree is: %d\n", height);

    // Don't forget to free the memory
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

Conclusion

The binary tree height is a fundamental concept that measures the tallest path from the top (root) to the bottom (leaf node) of the tree. It tells us how many levels the tree has and impacts its efficiency. A balanced tree, with similar levels, ensures quicker operations like searching and insertion since it takes fewer steps to find or add elements. In contrast, an imbalanced tree, with uneven levels, can slow down these operations as it requires more steps to reach the desired node.

Understanding and managing the height of a binary tree is essential in optimizing data structures and algorithms to efficiently handle large datasets. By maintaining balance, we can keep the height logarithmic, ensuring the tree remains efficient even with a substantial number of elements.

FAQS

1. What is the minimum height of binary tree?

The minimum height of binary tree occurs when all the nodes are packed to the left or right, forming a straight line. The minimum height is equal to the number of nodes minus one. In other words, for n nodes, the minimum height of the binary tree is n - 1.

2. What does the height of tree in data structure mean?

In data structures, the height of a tree represents the length of the longest path from the root node to the leaf node. It measures the depth of the tree and determines its overall structural complexity, impacting the efficiency of various tree operations.

3. What is the height and depth of a tree?

The height of a tree is the length of the longest path from the root to a leaf node, while the depth of a node is the length of its path to the root.