Trees — Data Structure & Algrorithm

So far, we've worked with linear data structures such as arrays, linked lists, stacks, and queues. In these structures, elements are generally arranged in a sequence.

But some data doesn't naturally form a straight line.

For example, think about a company's organizational structure:

              CEO
             /   \
          Manager Manager
          /  \       \
       John  Jason    Alex

The CEO has managers, and each manager has employees.

This kind of hierarchical structure is called a tree.

What is a Tree?

A tree is a non-linear data structure made up of nodes connected by edges.

A tree starts with one special node called the root.

For example:

              10
             /  \
            20   30
           / \     \
          40  50    60

Here:

10 → Root
20, 30 → Children of 10
40, 50 → Children of 20
60 → Child of 30

Unlike a linked list, a tree can branch into multiple directions.

Tree Terminology

Before working with trees, you need to understand some basic terms.

Node

A node is an individual element in a tree.

For example:

       10
      /
     20

Both 10 and 20 are nodes.

Root

The root is the topmost node in a tree.

       10
      /  \
     20   30

Here, 10 is the root.

Every tree has exactly one root.

Parent

A node directly connected above another node is its parent.

       10
      /
     20

10 is the parent of 20.

Child

A node directly connected below another node is its child.

       10
      /  \
     20   30

20 and 30 are children of 10.

Siblings

Nodes that have the same parent are called siblings.

       10
      /  \
     20   30

20 and 30 are siblings.

Leaf Node

A node that doesn't have any children is called a leaf node.

The leaf nodes are:

20? No, 20 has a child.
30
40

So 30 and 40 are leaf nodes.

Edge

An edge is the connection between two nodes.

10
|
20

The line connecting 10 and 20 is an edge.

A tree with n nodes always has:

n - 1

edges.

Depth

The depth of a node represents how far it is from the root.

For example:

              10       Depth 0
             /  \
            20   30    Depth 1
           / \
          40  50       Depth 2

So:

10 → Depth 0
20 → Depth 1
30 → Depth 1
40 → Depth 2
50 → Depth 2

The root has depth 0.

Height

The height of a node represents the longest path from that node down to a leaf.

For example:

The height of 10 depends on the convention being used.

If height is measured by edges:

10 → 20 → 30

there are two edges, so the height is 2.

The height of the tree is the height of its root.

Subtree

A node and all of its descendants form a subtree.

For example:

The subtree rooted at 20 is:

        20
       /  \
      40   50

Thinking about trees as collections of smaller subtrees becomes very useful when we study recursion and tree algorithms.

Creating a Tree Node in Java

A simple tree node can be created like this:

class Node {
    int data;

    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

Here, each node has:

data  → stores the value
left  → points to the left child
right → points to the right child

This particular structure is commonly used for a binary tree, where each node can have at most two children.

Creating a Simple Tree

Let's create this tree:

In Java:

Node root = new Node(10);

root.left = new Node(20);
root.right = new Node(30);

root.left.left = new Node(40);
root.left.right = new Node(50);

The root variable points to the first node:

root
 ↓
10

From there, we can reach every other node.

Trees Are Recursive Structures

One important thing about trees is that they are naturally recursive.

Consider:

The entire tree contains:

Root
├── Left Subtree
└── Right Subtree

The left subtree is:

       20
      /  \
     40   50

And the right subtree is:

Each subtree is itself a smaller tree.

This is why recursion is used so often when working with trees.

Traversing a Tree

Tree traversal means visiting every node in a tree.

There are several important traversal methods.

The most common ones are:

Preorder
Inorder
Postorder
Level Order

The first three are usually implemented using depth-first traversal, while level order uses breadth-first traversal.

Preorder Traversal

In preorder traversal, we process:

Root
Left
Right

For this tree:

Preorder gives:

10 → 20 → 40 → 50 → 30

The general pattern is:

Visit root
↓
Traverse left subtree
↓
Traverse right subtree

In Java:

static void preorder(Node root) {

    if (root == null) {
        return;
    }

    System.out.println(root.data);

    preorder(root.left);
    preorder(root.right);
}

Inorder Traversal

In inorder traversal, we process:

Left
Root
Right

For the same tree:

The inorder traversal is:

40 → 20 → 50 → 10 → 30

The Java implementation is:

static void inorder(Node root) {

    if (root == null) {
        return;
    }

    inorder(root.left);

    System.out.println(root.data);

    inorder(root.right);
}

Inorder traversal becomes particularly important with Binary Search Trees, because it visits their values in sorted order.

Postorder Traversal

In postorder traversal, we process:

Left
Right
Root

For our tree:

The postorder traversal is:

40 → 50 → 20 → 30 → 10

The Java implementation is:

static void postorder(Node root) {

    if (root == null) {
        return;
    }

    postorder(root.left);
    postorder(root.right);

    System.out.println(root.data);
}

Level Order Traversal

Instead of going deep into one branch, level order traversal visits nodes level by level.

For:

the order is:

10 → 20 → 30 → 40 → 50

We usually use a queue to implement level order traversal.

import java.util.LinkedList;
import java.util.Queue;

static void levelOrder(Node root) {

    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();

    queue.add(root);

    while (!queue.isEmpty()) {

        Node current = queue.remove();

        System.out.println(current.data);

        if (current.left != null) {
            queue.add(current.left);
        }

        if (current.right != null) {
            queue.add(current.right);
        }
    }
}

This is a great example of how different data structures work together.

Tree + Queue → Level Order Traversal

Binary Tree

A binary tree is a tree where each node can have at most two children.

The children are usually called:

Left Child
Right Child

For example:

Each node has zero, one, or two children.

A binary tree does not necessarily have to be sorted.

Binary Search Tree

A Binary Search Tree, or BST, is a special type of binary tree that follows an ordering rule.

For every node:

Left subtree < Node < Right subtree

For example:

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Everything smaller than 50 is on the left.

Everything larger than 50 is on the right.

This property allows efficient searching when the tree is balanced.

Tree vs Graph

Trees and graphs are both non-linear data structures, but they have important differences.

A tree:

        10
       /  \
      20   30

has a hierarchical structure and does not contain cycles.

A graph can have much more general connections:

A ─── B
│   / │
│  /  │
C ─── D

Graphs can contain cycles and don't necessarily have a single root.

We'll study graphs separately.

Real-Life Examples of Trees

Trees appear everywhere in computer science.

File Systems

A computer's file system can be represented as a tree:

Computer
├── Documents
│   ├── Resume.pdf
│   └── Notes.txt
├── Pictures
│   ├── Photo1.jpg
│   └── Photo2.jpg
└── Videos

The root could be the main directory, and folders become child nodes.

Company Hierarchy

CEO
├── Manager
│   ├── John
│   └── Jason
└── Manager
    ├── Alex
    └── Michael

HTML DOM

A web page is represented internally as a hierarchical structure.

For example:

HTML
├── Head
└── Body
    ├── Header
    ├── Main
    └── Footer

This is another tree-like structure.

Tree Applications

Trees are used in many areas, including:

File systems
Database indexes
HTML DOM
Autocomplete systems
Expression parsing
Artificial intelligence
Searching
Sorting
Game decision systems
Network routing
Compilers

Different types of trees are designed for different problems.

Tree Time Complexity

The complexity depends heavily on the operation and the type of tree.

For a tree with n nodes, simply visiting every node takes:

O(n)

because every node needs to be processed.

For a balanced Binary Search Tree, searching can typically take:

O(log n)

But if the tree becomes heavily unbalanced:

it starts behaving more like a linked list, and searching can become:

O(n)

This is why tree balance is an important topic in advanced DSA.

A Complete Example

Let's create a binary tree and perform preorder traversal:

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static void preorder(Node root) {

        if (root == null) {
            return;
        }

        System.out.print(root.data + " ");

        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {

        Node root = new Node(10);

        root.left = new Node(20);
        root.right = new Node(30);

        root.left.left = new Node(40);
        root.left.right = new Node(50);

        preorder(root);
    }
}

Output:

10 20 40 50 30

The recursive calls allow us to move through the entire tree.

The Main Idea

A tree is a non-linear hierarchical data structure made up of nodes connected by edges.

The most important terms to remember are:

Root
Parent
Child
Sibling
Leaf
Edge
Depth
Height
Subtree

And some of the most important tree concepts you'll encounter in DSA are:

Binary Tree
Binary Search Tree
Tree Traversals
Preorder
Inorder
Postorder
Level Order

The basic structure looks like:

              Root
             /    \
          Child   Child
          /  \
       Leaf   Leaf

A tree organizes data hierarchically, where nodes can have relationships with other nodes through parent-child connections.

Once you understand how nodes, children, roots, and subtrees work, concepts such as Binary Trees, Binary Search Trees, Heaps, AVL Trees, Tries, and advanced tree algorithms become much easier to learn.