Tree Terminology (Root, Leaf, Height, Degree) | Data Structures

Moving beyond linear structures (Arrays, Linked Lists, Stacks), a Tree is a non-linear, hierarchical data structure composed of nodes connected by directed edges.

Anatomy of a Tree

                    [ A ]               <-- Level 0 (Root)
                   /     \
                [ B ]   [ C ]           <-- Level 1
               /    \       \
            [ D ]  [ E ]    [ F ]       <-- Level 2 (Leaves)

Essential Tree Terms:

Root: The topmost node of the tree. It has no incoming edges (no parent). Every tree has exactly one root (A).
Edge: The directed link connecting a parent node to a child node. A tree with N nodes always has exactly N - 1 edges.
Parent / Child: If a node connects to another node below it, the top node is the parent (B is parent of D and E).
Siblings: Nodes that share the exact same parent (D and E are siblings).
Leaf (External Node): A node with zero children (D, E, F).
Internal Node: A node with at least one child (A, B, C).
Degree of a Node: The number of children a node has (Degree of B is 2; Degree of D is 0).
Degree of a Tree: The maximum degree of any node in the tree.

Depth vs Height: A Crucial Distinction

Many developers confuse Depth and Height:

Depth: Measures downward from Root to Node (Root depth = 0)
Height: Measures upward from Node down to deepest Leaf (Leaf height = 0)

Metric	Measured From	Definition	Formula
Depth of Node X	Root `→ X`	Number of edges from Root down to X	`depth(root) = 0`
Height of Node X	`X →` Deepest Leaf	Number of edges on longest downward path to a leaf	`height(leaf) = 0`
Height of Tree	Root `→` Deepest Leaf	The height of the root node	Max depth of any node

In the diagram above:

Depth of A: 0
Depth of E: 2
Height of B: 1 (edges to D or E)
Height of Tree: 2

Recursive Definition of a Tree

A tree is mathematically defined as:

A root node R.
Zero or more disjoint subtrees T_1, T_2, ..., T_k, each of which is itself a valid tree!

Because trees are recursively defined, almost all tree algorithms (traversal, depth calculation, search) are naturally expressed using recursion.

Summary

Trees organize data hierarchically with parent-child relationships.
A tree with N nodes always contains exactly N - 1 edges and no cycles.
Depth measures distance from root; Height measures distance to the deepest leaf.