Tree Data Structure: Introduction Tutorial

What Is a Tree Data Structure?

A tree is a non-linear data structure used to represent hierarchical relationships between elements. Unlike arrays, linked lists, stacks, and queues, where elements are generally arranged in a linear sequence, a tree allows one element to connect to multiple other elements.

Trees are made up of nodes connected by edges. One node is typically designated as the starting point, called the root. From the root, other nodes form branches and subtrees.

In this example, A is the root. B and C are its children, while D, E, and F are lower-level nodes in the hierarchy.

Why Are Trees Used?

Many real-world systems contain hierarchical information rather than simple sequences. Trees provide a natural way to model this type of data.

File and folder systems
HTML and DOM structures
Organization hierarchies
Database indexing
Search and sorting algorithms
Compiler syntax structures
Decision-making systems
Network and routing structures

A tree allows applications to organize related elements while preserving the relationships between parent and child elements.

Basic Structure of a Tree

A tree consists of nodes and edges. Each node stores data and may contain references to one or more child nodes, depending on the type of tree.

             Root
              A
            /   \
           B     C
          / \     \
         D   E     F

Nodes  : A, B, C, D, E, F
Edges  : A-B, A-C, B-D, B-E, C-F

An edge represents a connection between two nodes. In a conventional tree, there is exactly one path between any two connected nodes.

Root Node

The root is the topmost node of a tree. It is the starting point from which the remaining nodes can be reached.

In this tree, A is the root. A tree normally has exactly one root when represented as a rooted tree.

Parent and Child Nodes

When two nodes are directly connected in a hierarchy, the node closer to the root is called the parent and the node below it is called the child.

A is the parent of B and C.
B is the parent of D and E.
D and E are children of B.
C has no children in this example.

Leaf Nodes

A leaf node is a node that does not have any children. Leaf nodes appear at the ends of branches.

D, E, and C are leaf nodes because none of them has a child.

Internal Nodes

An internal node is a node that has at least one child. In the example above, A and B are internal nodes because they have children.

The root can also be an internal node when the tree contains more than one node.

Edges in a Tree

An edge is a connection between two nodes. If a tree contains n nodes and is connected, it contains exactly n - 1 edges.

        A
       / \
      B   C
     / \
    D   E

Nodes = 5
Edges = 4

This relationship is one of the fundamental properties of trees.

Path in a Tree

A path is a sequence of connected nodes. For example, in the following tree, the path from A to E is:

        A
       / \
      B   C
     / \
    D   E

Path from A to E:

A → B → E

In a tree, there is exactly one simple path between any two nodes.

Depth of a Node

The depth of a node represents its distance from the root, usually measured by the number of edges along the path from the root to that node.

        A          Depth 0
       / \
      B   C        Depth 1
     / \
    D   E          Depth 2

The root has depth 0.
B and C have depth 1.
D and E have depth 2.

Height of a Tree

The height of a tree is the number of edges on the longest path from the root to a leaf. Under this common definition, a tree containing only the root has height 0.

        A
       / \
      B   C
     /
    D

Longest path:

A → B → D

Height = 2

Height and depth describe different properties. Depth measures how far a particular node is from the root, while height describes the longest downward distance within a tree or subtree.

Subtree

A subtree is a node together with all of its descendants. Every node in a tree can be considered the root of its own subtree.

The subtree rooted at B contains B, D, and E.

      B
     / \
    D   E

Important Tree Properties

Several properties distinguish trees from other data structures and graph structures.

Property	Description
Root	The topmost node in a rooted tree
Nodes	Elements that store data
Edges	Connections between nodes
Leaf	A node with no children
Depth	Distance from the root to a node
Height	Longest downward path measured in edges

Types of Trees

Trees can be classified in several ways depending on the number of children allowed, ordering rules, balancing requirements, and the operations they are designed to support.

Binary Tree

A binary tree is a tree in which each node can have at most two children, commonly called the left child and right child.

Binary Search Tree

A Binary Search Tree, or BST, is a binary tree that follows an ordering rule. Values in the left subtree are generally smaller than the node, while values in the right subtree are generally greater, depending on the duplicate-value policy.

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

Balanced Tree

A balanced tree maintains its height within a controlled range so that operations do not unnecessarily degrade because of an extremely skewed structure.

AVL trees and Red-Black trees are examples of self-balancing binary search trees.

Heap

A heap is a specialized tree-based data structure that follows a heap-order property. Min-heaps and max-heaps are commonly used to implement priority queues.

Trie

A trie is a tree-like data structure designed for storing strings and prefixes. It is useful for operations such as prefix searching and autocomplete.

Tree vs Linear Data Structures

Linear data structures arrange elements in a sequence, while trees represent branching relationships.

Characteristic	Linear Structure	Tree
Organization	Sequential	Hierarchical
Branching	Usually no branching	Nodes can have multiple children
Examples	Array, linked list, stack, queue	Binary tree, BST, heap, trie

Representing a Binary Tree in JavaScript

A binary tree can be represented using a class or object where each node stores its value and references to its left and right children.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(50);

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

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

root.right.left = new Node(60);
root.right.right = new Node(80);

The references between nodes create the tree structure. A null reference indicates that a particular child does not exist.

Basic Tree Operations

The operations supported by a tree depend on its specific type. Common operations include:

Inserting a node
Searching for a value
Deleting a node
Traversing the tree
Finding minimum or maximum values
Calculating height and depth
Finding relationships between nodes

For example, a Binary Search Tree provides ordering rules that can make searching and insertion more efficient when the tree remains balanced.

Tree Traversal

Traversal means visiting the nodes of a tree according to a particular order. Binary trees commonly use four traversal strategies.

Traversal	Order	Approach
Preorder	Root → Left → Right	Depth-first
Inorder	Left → Root → Right	Depth-first
Postorder	Left → Right → Root	Depth-first
Level-order	Level by level	Breadth-first

Trees and Graphs

A tree is a specialized form of graph. A connected tree has no cycles and has exactly one simple path between any two nodes.

This distinction becomes important when studying graph algorithms because many tree traversal and graph traversal techniques share similar concepts while operating under different structural constraints.

Where Trees Are Used

Tree structures appear throughout software systems because hierarchical relationships are common in both application data and system internals.

Operating system file systems
HTML DOM and document structures
Database indexes
Search engines and autocomplete systems
Compiler syntax trees
Decision trees
Priority queues using heaps
Hierarchical application menus
Routing and network structures

Common Tree Concepts to Learn Next

Once the basic tree model is understood, the next concepts usually involve tree terminology, binary trees, traversal algorithms, Binary Search Trees, and balanced trees.

Tree terminology and properties
Binary trees
Tree traversal
Inorder, preorder, and postorder traversal
Level-order traversal
Binary Search Trees
AVL trees
Red-Black trees
Heaps and priority queues

Common Beginner Mistakes

Confusing the root node with a leaf node.
Using depth and height as if they describe the same measurement.
Assuming every tree is a binary tree.
Assuming every binary tree is a Binary Search Tree.
Assuming a tree must always be balanced.
Forgetting that a leaf node has no children.
Confusing tree traversal with tree searching.
Assuming all tree operations have the same complexity regardless of tree type.

Key Takeaways

A tree is a non-linear data structure used to represent hierarchical relationships.
Trees consist of nodes connected by edges.
The root is the topmost node in a rooted tree.
Nodes can have parents, children, siblings, and descendants.
A leaf node has no children.
Depth measures distance from the root, while height measures the longest downward path.
A tree with n nodes has n - 1 edges when it is connected.
Binary trees allow each node to have at most two children.
Binary Search Trees add ordering rules to binary trees.
Different tree types are designed for different operations and use cases.

Topics

Tree Data Structure: Introduction