Height of Tree (Data Structure)

Introduction

The height of a tree is an important concept in data structures. It is a way of organizing a tree in a data structure in an orderly and orderly manner. A tree data structure consists of an organized hierarchy of branches, in which each branch may relate to one or more subbranches.

Tree height is an important characteristic that affects the structure and tactical activities inside the tree. The height attribute shows the number of nodes (branches) of the tree and the relationship between the branches.

This type of data structure can be represented in a variety of ways, such as a consonance-based tree, an ICD tree, or a stacked tree.

Height of tree formula

Height of Tree = Max(Height of Left Subtree, Height of Right Subtree) + 1

How to Find the Height of a Tree in Data Structure?

• Recursive Approach
• Iterative Approach

Recursive Approach

1. If the tree is empty or null, return 0 (base case).
2. If the tree is not empty, recursively calculate the height of the left and right subtrees.
3. Return the maximum height among the left and right subtrees, plus 1 (to account for the current level).

An algorithm in Pesudo code

function calculate_tree_height(node):
if node is null or empty:
return 0
else:
left_height = calculate_tree_height(node.left)
right_height = calculate_tree_height(node.right)
return max(left_height, right_height) + 1

Python Code

# Node definition for a binary tree
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Function to calculate the height of a tree
def calculate_tree_height(root):
    if root is None:
        return 0
    else:
        left_height = calculate_tree_height(root.left)
        right_height = calculate_tree_height(root.right)
        return max(left_height, right_height) + 1

# Example usage
# Create a binary tree
"""
        1
       / \
      2   3
     / \
    4   5
   /
  6
"""
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(6)

# Calculate the height of the tree
height = calculate_tree_height(root)
print("Height of the tree:", height)

Output

Height of the tree: 4

Java Code

// Node definition for a binary tree
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Class to calculate the height of a tree
class TreeHeightCalculator {
    public static int calculateTreeHeight(Node root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = calculateTreeHeight(root.left);
            int rightHeight = calculateTreeHeight(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    public static void main(String[] args) {
        // Create a binary tree
        /*
                1
               / \
              2   3
             / \
            4   5
           /
          6
        */
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(6);

        // Calculate the height of the tree
        int height = calculateTreeHeight(root);
        System.out.println("Height of the tree: " + height);
    }
}

Output

Height of the tree: 4

C++ Code

#include <iostream>
using namespace std;

// Node definition for a binary tree
struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int value) {
        this->value = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to calculate the height of a tree
int calculate_tree_height(Node* root) {
    if (root == nullptr) {
        return 0;
    } else {
        int left_height = calculate_tree_height(root->left);
        int right_height = calculate_tree_height(root->right);
        return max(left_height, right_height) + 1;
    }
}

int main() {
    // Create a binary tree
    /*
            1
           / \
          2   3
         / \
        4   5
       /
      6
    */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(6);

    // Calculate the height of the tree
    int height = calculate_tree_height(root);
    cout << "Height of the tree: " << height << endl;

    return 0;
}

Output

Height of the tree: 4

Iterative Approach

1. If the tree is empty or null, return 0 (base case).
2. Create an empty queue and enqueue the root node.
3. Initialize the height as 0.
4. Repeat the following steps while the queue is not empty:
   • Increment the height by 1.
   • Get the size of the current level of the queue.
   • Process all nodes in the current level by dequeuing them and enqueueing their child nodes.
5. Return the height as the height of the tree.

An algorithm in Pesudo code

function calculate_tree_height(root):
    if root is null or empty:
        return 0
        
    queue = create_empty_queue()
    enqueue(root)
    height = 0
    
    while queue is not empty:
        height += 1
        level_size = get_size_of_current_level(queue)
        
        for i = 1 to level_size:
            node = dequeue(queue)
            
            if node has left child:
                enqueue(left child)
                
            if node has right child:
                enqueue(right child)
    
    return height

Python Code

# Node definition for a binary tree
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Function to calculate the height of a tree
def calculate_tree_height(root):
    if root is None:
        return 0
    
    height = 0
    level = [root]
    
    while level:
        height += 1
        next_level = []
        
        for node in level:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        
        level = next_level
    
    return height

# Example usage
# Create a binary tree
"""
        1
       / \
      2   3
     / \
    4   5
   /
  6
"""
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(6)

# Calculate the height of the tree
height = calculate_tree_height(root)
print("Height of the tree:", height)

Output

Height of the tree: 4

Java Code

import java.util.LinkedList;
import java.util.Queue;

// Node definition for a binary tree
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Class to calculate the height of a tree
class TreeHeightCalculator {
    public static int calculateTreeHeight(Node root) {
        if (root == null) {
            return 0;
        }
        
        int height = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            height++;
            int levelSize = queue.size();
            
            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();
                
                if (node.left != null) {
                    queue.add(node.left);
                }
                
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        
        return height;
    }

    public static void main(String[] args) {
        // Create a binary tree
        /*
                1
               / \
              2   3
             / \
            4   5
           /
          6
        */
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(6);

        // Calculate the height of the tree
        int height = calculateTreeHeight(root);
        System.out.println("Height of the tree: " + height);
    }
}

Output

Height of the tree: 4

C++ Code

#include <iostream>
#include <queue>
using namespace std;

// Node definition for a binary tree
struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int value) {
        this->value = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to calculate the height of a tree
int calculate_tree_height(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    
    int height = 0;
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        height++;
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; i++) {
            Node* node = q.front();
            q.pop();
            
            if (node->left != nullptr) {
                q.push(node->left);
            }
            
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
    }
    
    return height;
}

int main() {
    // Create a binary tree
    /*
            1
           / \
          2   3
         / \
        4   5
       /
      6
    */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(6);

    // Calculate the height of the tree
    int height = calculate_tree_height(root);
    cout << "Height of the tree: " << height << endl;

    return 0;
}

Output

Height of the tree: 4

Note: It’s important to note that the height of a tree is different from the depth of a tree. The depth refers to the length of the path from the root node to the current node, whereas the height measures the length of the longest path from the root to any leaf.