Height of Tree 🎯

Welcome to our deep dive into understanding the Height of a Tree! This lesson is designed for beginners and intermediates, so let's get started with some basics.

What is a Tree? 📝

A tree is a data structure that mimics the structure of a tree in nature. It consists of nodes connected by edges. Each node can have a value, and each node can have zero or more children nodes.

Why Understand Tree Height? 💡

Knowing the height of a tree is essential in many algorithms and data structures. It helps us determine the complexity of certain operations, manage the tree efficiently, and find the maximum depth of the tree.

Understanding Tree Height 📝

The height of a tree is defined as the number of edges from the root node to the farthest leaf node. In simple terms, it's the tallest path from the root node to any leaf node.

Calculating Tree Height 🎯

There are two ways to calculate the height of a tree:

Direct Method: This involves traversing the tree from the root node and counting the number of edges until we reach the deepest leaf node.
Indirect Method (Using Depth): This method calculates the height of each subtree and chooses the maximum depth as the height of the tree.

Example 📝

Let's consider a simple binary tree:

   1
  / \
 2   3

Direct Method: Traverse the tree, and we find the deepest leaf node is 3, which is 2 edges away from the root node. So, the height of the tree is 2.
Indirect Method (Using Depth): Calculate the height of each subtree.
- Height of left subtree (subtree with node 2): 1 (since 2 is the only node in this subtree)
- Height of right subtree (subtree with nodes 3): 1 (since 3 is the only node in this subtree)
- The maximum height is 1 (from both subtrees), so the height of the tree is 1.

However, in real-world applications, the direct method is more commonly used due to its simplicity and efficiency.

Code Examples 💻

Example 1: Direct Method - C++

cpp

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    int height;

    Node(int val) {
        data = val;
        left = right = NULL;
        height = 1;
    }
};

int height(Node* root) {
    if (root == NULL) return 0;
    return root->height;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int heightTree(Node* root) {
    if (root == NULL) return 0;

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

    root->height = max(leftHeight, rightHeight) + 1;
    return root->height;
}

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

    cout << heightTree(root) << endl;  // Output: 2

    return 0;
}

Example 2: Direct Method - Python

python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def height(node):
    if node is None:
        return 0
    return node.height

def max_height(a, b):
    return a > b and a or b

def height_tree(node):
    if node is None:
        return 0

    left_height = height(node.left)
    right_height = height(node.right)

    node.height = max_height(left_height, right_height) + 1
    return node.height

root = Node(1)
root.left = Node(2)
root.right = Node(3)

print(height_tree(root))  # Output: 2

Wrap Up 📝

Now that we've explored the concept of the height of a tree, you're ready to tackle more complex data structures and algorithms!

Remember, practice makes perfect, so take time to experiment with different trees and observe their heights. Keep an eye out for upcoming lessons here at CodeYourCraft, where we'll continue to delve deeper into the fascinating world of data structures and algorithms. 🎉

Good luck on your coding journey, and happy learning! 💻🚀