Tree: Definitions - Height

Definition

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

If a tree has only one node (the root), its height is commonly taken as 0 because there are no edges below it.
If a tree is empty, its height is often defined as -1 in some academic conventions, though some texts may define it as 0 depending on the context.
Height is measured in terms of edges, not nodes.

Example

Consider the following tree:

Longest path from root A to a leaf is A -> B -> D
This path has 2 edges
Therefore, the height of the tree = 2

Main Content

1. First Concept: Height of a Node

The height of a node is the number of edges on the longest downward path from that node to a leaf.
A leaf node has height 0 because there is no edge below it.

Example

In the tree below:

Height of D = 0
Height of E = 0
Height of B = 1, because longest path is B -> D or B -> E
Height of C = 0
Height of A = 2, because longest path is A -> B -> D

Why it matters

Height of nodes is used in recursive tree algorithms.
It helps determine how far a node is from the deepest leaf below it.
It is used in balancing trees and calculating structural properties.

2. Second Concept: Height of a Tree

The height of a tree is simply the height of its root node.
It represents the maximum depth of the tree structure.
A taller tree usually means more levels and potentially more time for traversal or searching.

Example

For this tree:

Root is 10
Longest path from root to leaf: 10 -> 5 -> 3
Number of edges = 2
So, tree height = 2

Important note

Some students confuse height with depth:
Height is measured upward from the deepest leaf to the root conceptually, but practically it means the longest downward path from node to leaf.
Depth of a node is the number of edges from the root to that node.
For the root node:
Depth = 0
Height = height of the entire tree

3. Third Concept: Height, Levels, and Depth Relationship

Level

usually refers to the position of a node in the tree, starting from the root.

Depth

of a node is the number of edges from the root to that node.

Height

of the tree is the maximum depth among all nodes.

Relationship

Root node depth = 0
Nodes one edge away from root have depth = 1
Nodes two edges away from root have depth = 2
The maximum depth of any node = height of the tree

Example

For the tree:

Depth of A = 0
Depth of B = 1
Depth of C = 1
Depth of D = 2
Depth of E = 2
Tree height = 2

Why this relationship is useful

It helps in understanding tree traversal and recursion.
It supports performance analysis of tree operations.
It is used in AVL trees and other self-balancing structures to maintain efficient height.

Working / Process

1. Start from the root node

To find the height of a tree, begin at the root.
The root is the topmost node and the reference point for measuring height.

2. Find the longest path to any leaf

Explore all root-to-leaf paths.
Identify the path with the maximum number of edges.
The length of that longest path is the tree’s height.

3. Use recursive calculation

For any node:
- Height of a leaf = 0
- Height of a non-leaf node = 1 + max(height of left subtree, height of right subtree) in a binary tree
This recursive rule is the most common method for calculating height in programs.

Example of recursive idea

height(node):
    if node is NULL:
        return -1
    if node is a leaf:
        return 0
    return 1 + max(height(left child), height(right child))

Example calculation

For this tree:

height(D) = 0
height(E) = 0
height(B) = 1 + max(0, 0) = 1
height(C) = 0
height(A) = 1 + max(1, 0) = 2

So the tree height is 2.

Advantages / Applications

Performance analysis of tree operations

Height directly affects searching, insertion, and deletion time in many trees.
Smaller height generally means faster operations.

Balancing trees

Balanced trees such as AVL trees and Red-Black trees control height to maintain efficiency.
Height is used to decide whether rebalancing is needed.

Practical use in real systems

Height is important in file systems, database indexing, syntax trees, and priority queues.
It helps measure and manage the structure of hierarchical data.

Summary

Height means the longest path from a node to a leaf measured in edges.
The height of a tree is the height of its root.
Height is a key measure for understanding tree efficiency and balance.
Important terms to remember: tree height, node height, leaf node, root node, depth