C++ Binary Tree Height Calculation

What Will You Learn in This Guide?

In this guide, you will learn how to calculate the height of a Binary Tree structure in C/C++ languages.
You will see step by step what the tree height means, the recursion used to find this value, and the implementation of this logic in real code.

Technical Summary

• Main Topic: Calculating Binary Tree height
• Approach: Recursive algorithm
• Time Complexity: O(N)
• Purpose: To find the maximum height by comparing the subtree heights of each node
• Application Area: Tree-based data structures, algorithm optimization

---

What is Height in Binary Tree?

The height of a binary tree is the number of edges of the longest path from the root node to the farthest leaf.**

For example:

    10
   /  \
 20    30
/  \
40 50

Burada en uzun yol (10 → 20 → 40) **3 kenar** içerir.  
Yani bu ağacın yüksekliği **3**’tür.

Formula:

Yükseklik(D) = 1 + max(Yükseklik(Sol), Yükseklik(Sağ))

---

1. Creating a Tree Node Structure

The structure to represent each tree node (Node) is as follows:

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

typedef struct Node {
    int value;
    struct Node *left, *right;
} Node;

• Explanation: value holds the value of the node, and left and right hold the child nodes.

---

2. Function to Calculate Height

This function recursively calculates the height of the left and right subtrees and adds +1 to the highest.

int tree_height(Node* root) {
    if (root == NULL)
        return 0; // Temel durum (base case)
    
    int sol_yukseklik = tree_height(root->left);
    int sag_yukseklik = tree_height(root->right);

    return (sol_yukseklik > sag_yukseklik ? sol_yukseklik : sag_yukseklik) + 1;
}

• Description: Subtrees are traversed with each call. Returns 0 for empty node, maximum bottom height +1 for others.

---

3. Main Program (main) – Sample Tree and Output

int main() {
    Node* root = (Node*) malloc(sizeof(Node));
    root->value = 10;
    root->left = (Node*) malloc(sizeof(Node));
    root->left->value = 20;
    root->right = (Node*) malloc(sizeof(Node));
    root->right->value = 30;
    root->left->left = (Node*) malloc(sizeof(Node));
    root->left->left->value = 40;
    root->left->right = (Node*) malloc(sizeof(Node));
    root->left->right->value = 50;

    printf("İkili Ağacın Yüksekliği: %d\n", tree_height(root));
    return 0;
}

• Expected Output:

İkili Ağacın Yüksekliği: 3

---

Algorithm Features

Feature	Description
Approach	Recursive
Time Complexity	O(N) — Each node is visited once
Memory Usage	O(h) — h = call stack as height of tree
Alternative Method	Iterative approach with BFS (Breadth First Search)
Scope	AVL is frequently used in balanced trees such as Red-Black Tree

---

Frequently Asked Questions (FAQ)

1. Are height and depth the same thing?

Height is the longest path from root to leaf. Depth is the distance of a particular node from the root.

2. What is the height of an empty tree?

According to the base case, if the root is NULL, its height is 0.

3. Why is the time complexity O(N)?

Because the algorithm visits each node only once.

4. Is there any difference between C and C++?

There is no max() function in C, so the if/else or ternary (?:) construct is used. In C++, std::max() can be used with the <algorithm> library.

5. How is it calculated with BFS?

Queue structure is used, the height is set to +1 when each level is completed.

---

Result

In this guide, you learned how to calculate Binary Tree height recursively in C/C++. This method is one of the most important parts of data structure and algorithm foundations.

You can try it now on the GenixNode platform to test performance measurements while working with tree structures.