Tree Data Structure – Introduction

In this tutorial, we’ll explore the Tree data structure, its terminologies, and the types of trees based on the number of children a node can have. This is a foundational topic for data structures, often used in technical interviews and essential for real-world programming tasks.

What is a Tree Data Structure?

A Tree is a non-linear data structure that consists of a collection of nodes connected via edges in a hierarchical fashion. Unlike linear data structures (like arrays and linked lists), where data is organized sequentially, a tree organizes data like a family hierarchy or an organizational chart.

Definition:

A Tree is a collection of nodes where:

One node is designated as the root.
Every node (except the root) has exactly one parent.
Nodes may have zero or more children.
Nodes are connected via edges.

Real-Life Analogy – Family Tree

Imagine a family tree:

Your great-grandfather is the root.
He has two sons, they are children nodes.
Each son might have children of their own, and so on.
This hierarchical structure mimics a Tree.

Tree Components and Terminologies

Let’s break down the essential parts of a tree:

1. Node

Each element of the tree is called a node. It stores data and has links to its children (if any).

2. Edge

An edge is the connection between two nodes. For example, the line connecting a parent and child.

3. Root Node

The topmost node of the tree. It has no parent. The tree grows from this node.

4. Leaf Node

A node with no children. It is at the end of a branch.

5. Internal Node

Any node that is not a leaf, i.e., it has at least one child.

6. Parent Node

A node that has one or more child nodes.

7. Child Node

A node that descends from another node (its parent).

8. Siblings

Nodes that share the same parent.

9. Ancestors

All nodes along the path from a given node up to the root.

10. Descendants

All nodes that descend from a given node.

11. Level

The depth of a node in the tree:

Root is at level 0.
Its children are at level 1.
And so on.

12. Neighbors

Nodes that are directly connected by an edge.

13. Subtree

Any node, along with its descendants, forms a subtree. Every node is the root of its own subtree.

Example Tree Illustration

Let’s consider the following example:

A is the root.
D, E, G are leaf nodes.
B, C are internal nodes.
Parent of E is B; Child of C is F.
Siblings of E: D
Ancestors of G: F → C → A
Descendants of B: D, E, G
Level of A: 0, B and C: 1, D, E, F: 2, G: 3
Neighbors of C: A and F

Cousins in a Tree

Two nodes are cousins if:

They are at the same level
But have different parents

From the example:

E and F are cousins.
D and E are siblings (not cousins).

Types of Trees Based on Children Count

1. Binary Tree

Each node has at most 2 children.
Children are referred to as left and right.

Examples:

        A
       / \
      B   C

A has two children: B and C → valid binary tree
B has no child → still valid

2. Ternary Tree

Each node has at most 3 children.

3. N-ary Tree

Each node can have at most N children.
N could be any number depending on application.

Special Binary Trees (Covered in Future Tutorials)

Binary Search Tree (BST) – Left child < parent < right child
AVL Tree – A self-balancing BST
Segment Tree, Trie, Heap, etc.

Important Notes

A tree with only one node is both the root and leaf.
If a tree has no internal node (i.e., no node with children), it means there is only one node in the tree.
Binary Tree is a fundamental structure and forms the base for many advanced trees like BSTs and Heaps.

Conclusion

Understanding a Tree and its terminologies is essential for solving complex problems in data structures and algorithms. The hierarchical structure makes it suitable for organizing data like file systems, organizational charts, and XML/JSON parsing.

If you’re preparing for interviews, especially in product-based companies, make sure you have a strong grasp of:

Tree concepts
Binary Trees and Binary Search Trees
Tree traversal techniques (preorder, inorder, postorder)