Tree Algorithms

A tree is a hierarchical data structure made up of nodes connected by edges. Unlike arrays or linked lists, which are linear, trees organize data in a parent-child relationship, making them ideal for representing structured or nested information.

Trees are widely used in areas such as file systems, databases, compilers, networking, and search algorithms.

What Is a Tree?

A tree consists of:

Nodes - individual elements that store data
Edges - connections between nodes
Root - the topmost node in the tree
Children - nodes directly connected below another node
Parent - the node directly above a child

A key property of trees is that there are no cycles - there is exactly one path between any two nodes.

Basic Terminology

Understanding tree terminology is essential before working with tree algorithms.

Root

The root is the topmost node in a tree. Every tree has exactly one root.

        Root

Parent and Child

If node A connects to node B below it:

A is the parent
B is the child

        A
       /
      B

Leaf Node

A leaf node is a node with no children.

      A
     / \
    B   C   ← B and C are leaves

Siblings

Nodes that share the same parent are called siblings.

      A
     / \
    B   C   ← siblings

Depth, Height, and Level

Depth

Depth of a node = number of edges from the root to that node
Root has depth 0

Depth:
Root → 0
Children → 1
Grandchildren → 2

Height

Height of a node = number of edges on the longest path from that node to a leaf
Height of the tree = height of the root

Leaf nodes → height 0
Root height → max depth in the tree

Level

Level is often defined as depth + 1
Root is at level 1

This is mostly used for visualization and level-order traversal.

Degree of a Node

The degree of a node is the number of children it has.

Leaf nodes have degree 0
A node with two children has degree 2

Types of Trees (High-Level Overview)

Here are common tree categories:

Tree Type	Description
General Tree	Any number of children per node
Binary Tree	At most two children per node
Binary Search Tree (BST)	Binary tree with ordering rules
Balanced Tree	Height kept minimal (AVL, Red-Black)
Heap	Complete binary tree with heap property

Why Trees Are Useful

Trees provide efficient solutions for problems involving:

Hierarchical data (file systems, HTML DOM)
Fast searching and sorting
Range queries and indexing
Expression parsing and evaluation

Their structure allows many operations to run in logarithmic time, which is far more efficient than linear approaches for large datasets.