Articles / DSA · Part 21

Trees: Definitions, Terminologies, and Properties

Learn the basics of tree data structures, including root, parent, child, leaf, degree, depth, height, and important tree properties with simple diagrams.

Trees: Definitions, Terminologies, and Properties

In the previous articles, we explored linear data structures such as arrays, linked lists, stacks, and queues.

But not all data needs to be arranged in a straight line.

Consider how a university is organised:

  • A university has different departments.
  • Each department has different courses.
  • Each course may have several students.

This kind of arrangement forms a hierarchy, where one element can be connected to several others.

In DSA, we use a data structure called a Tree to represent such relationships.

1. What Is a Tree?

A Tree is a non-linear data structure made up of elements called nodes, connected through edges.

Each node stores data and may be connected to other nodes.

Unlike arrays and linked lists, where elements are arranged in a sequence, trees allow data to branch into different directions.

Example:

Consider this tree:

          A
        / | \
       B  C  D
      / \
     E   F

Here, A is connected to B, C, and D. B is further connected to E and F.

This structure is called a tree because it represents data in a branching form.

2. Basic Terminologies of Trees

Let’s understand the important terms using the same example.

A. Node

A Node is an individual element of a tree that stores data.

In our example, A, B, C, D, E, and F are all nodes.

B. Root Node

The Root is the topmost node of a tree.

It is the starting point of the tree and has no parent.

In our example, A is the root node.

C. Parent and Child

  • Parent: A node that has one or more nodes directly below it.
  • Child: A node directly connected below another node.

For example:

  • A is the parent of B, C, and D.
  • B is the parent of E and F.
  • E and F are children of B.

D. Siblings

Siblings are nodes that share the same parent.

For example, B, C, and D are siblings because they all have the same parent, A.

Similarly, E and F are siblings because their parent is B.

E. Leaf Node

A Leaf Node is a node that has no children.

In our example, C, D, E, and F are leaf nodes.

A leaf node is also called an <abbr title=”Another name for a leaf node; a node that has no children.”>External Node</abbr>.

F. Internal Node

An Internal Node is a node that has at least one child.

In our example, A and B are internal nodes.

G. Edge

An Edge is the connection between two nodes.

In our example, the connections A–B, A–C, A–D, B–E, and B–F are edges.

A tree with 6 nodes has 5 edges.

H. Degree of a Node

The Degree of a Node is the number of children that node has.

For example:

  • Degree of A = 3
  • Degree of B = 2
  • Degree of C = 0
  • Degree of D = 0

A leaf node always has a degree of 0.

The Degree of a Tree is the highest degree among all its nodes.

In our example, the degree of the tree is 3.

I. Path

A Path is a sequence of nodes connected through edges.

For example:

A → B → E

This is a path from A to E.

J. Ancestor and Descendant

  • Ancestor: Any node that appears above a particular node along the path to the root.
  • Descendant: Any node that appears below a particular node.

For example:

  • A and B are ancestors of E.
  • E and F are descendants of B.

K. Subtree

A Subtree is a smaller tree formed by a node and all its descendants.

In our example:

       B
      / \
     E   F

This is a subtree of the original tree.

3. Depth, Level, and Height

These three terms describe the position and size of a tree. They are closely related but have different meanings.

Consider this tree:

          A
         / \
        B   C
       / \
      D   E

A. Depth

The Depth of a node is the number of edges between the root and that node.

  • Depth of A = 0
  • Depth of B = 1
  • Depth of D = 2

The root always has a depth of 0.

B. Level

The Level represents the position of a node in the tree.

For this article, we count the root as Level 1.

Level 1:       A

Level 2:     B   C

Level 3:    D E

Therefore:

  • A is at Level 1.
  • B and C are at Level 2.
  • D and E are at Level 3.

Remember: Level = Depth + 1 under this counting convention.

C. Height

The Height of a node is the number of edges on the longest path from that node down to a leaf.

For example:

  • Height of D = 0
  • Height of B = 1
  • Height of A = 2

The Height of a Tree is the height of its root node.

Therefore, the height of this tree is 2.

Note: Some books count levels or height using the number of nodes instead of edges. Here, we consistently measure depth and height using edges.

4. Important Properties of Trees

Trees follow some important rules:

  1. A non-empty tree has exactly one root node.
  2. Every node except the root has exactly one parent.
  3. A tree does not contain a cycle. A cycle is a path that starts and ends at the same node.
  4. There is exactly one path between any two nodes in a tree.
  5. A tree containing n nodes always has n - 1 edges.
  6. A node can have zero or more children.

Why Does a Tree Have n – 1 Edges?

Let’s understand this with an example.

Consider a tree containing 5 nodes:

        A
       / \
      B   C
     / \
    D   E

Count the connections:

  • A–B
  • A–C
  • B–D
  • B–E

There are 5 nodes and 4 edges.

Therefore:

[
\text{Number of edges} = n – 1
]

[
= 5 – 1 = 4
]

This rule applies to every non-empty tree.

5. Applications of Trees

Trees are used in many areas of computer science.

  • File Systems: Organising folders and files into directories and subdirectories.
  • Organisation Charts: Representing relationships between employees and managers.
  • Databases: Organising and searching large amounts of data using structures such as B-Trees.
  • Web Development: Representing HTML documents through the Document Object Model (DOM).
  • Decision Making: Representing possible choices and their outcomes using decision trees.

Conclusion

A Tree is a non-linear data structure that organises data through nodes and edges.

We learned its important terminologies, including root, parent, child, sibling, leaf, degree, depth, level, and height.

We also explored the properties of trees, especially the rule that a tree containing n nodes has exactly n - 1 edges.

In the next article, we’ll explore Binary Trees: Representation, Traversals, and Applications, where we’ll learn how trees with at most two children per node work.


Further reading: GeeksforGeeks – Tree Data Structure · Kansas State University – Trees Summary

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DSA · Part 14

Searching and Sorting Algorithms Compared

Compare Linear Search, Binary Search, and five popular sorting algorithms. Understand their working methods, time complexities, and when to use each one.

4 min read

Ask Farhan

Ask anything about Farhan