Overview

A tree is a non-linear data structure that organizes information hierarchically. Unlike arrays and linked lists, trees branch from a root into parent and child nodes. This structure naturally represents folders, navigation menus, document elements, and organization charts.

Key concepts

• The root is the topmost node
• Edges connect parent nodes to child nodes
• Leaf nodes have no children
• DFS and BFS are the two foundational traversal strategies

What is a Tree?

A tree is a collection of nodes connected by edges. It begins with one root, and every other node appears beneath it in the hierarchy.

        A
       /       B   C
     /        D   E   F

• A is the root
• B and C are children of A
• D and E are children of B
• F is a child of C
• D, E, and F are leaves

Why do we need Trees?

A computer containing every file in one long list would be difficult to navigate. Directories solve this by nesting folders inside other folders. Trees provide the same natural organization whenever information has parent-child relationships.

Important Tree terminology

Root Node

The root is the topmost node and the starting point for navigating the tree.

Parent and Child

A parent has one or more nodes directly beneath it. Those connected nodes are its children. In the example, A is the parent of B and C.

Leaf Node

A leaf is a node with no children. D, E, and F are leaves in the example tree.

Edge

An edge is a connection between two nodes, such as the connection from A to B.

Depth and Height

A node's depth is its number of edges from the root. A tree's height is the number of edges on its longest root-to-leaf path.

Creating a simple Tree in JavaScript

A general tree node can store a value and an array of children.

const tree = {
  value: "A",
  children: [
    {
      value: "B",
      children: [
        { value: "D", children: [] },
        { value: "E", children: [] }
      ]
    },
    {
      value: "C",
      children: [
        { value: "F", children: [] }
      ]
    }
  ]
};

console.log(tree.value); // A

Tree Traversal

Traversal means visiting the nodes of a tree in a systematic order.

Depth-First Search (DFS)

DFS explores one branch as deeply as possible before returning to explore another branch.

A → B → D → E → C → F

function depthFirst(node) {
  console.log(node.value);

  for (const child of node.children) {
    depthFirst(child);
  }
}

Breadth-First Search (BFS)

BFS visits nodes one level at a time using a queue.

A → B → C → D → E → F

function breadthFirst(root) {
  const queue = [root];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    console.log(node.value);
    queue.push(...node.children);
  }
}

Types of Trees

• General Tree: nodes may have any number of children
• Binary Tree: each node has at most two children
• Binary Search Tree: ordered binary tree
• AVL Tree: self-balancing binary search tree
• B-Tree: balanced multiway tree used in storage systems
• Trie: character-based tree used for prefixes

Beginners should first understand general tree structure and traversal before moving to specialized tree types.

Time complexity

Traversing or searching an ordinary unordered tree may require visiting every node, which takes O(n). Ordered balanced trees can provide faster operations.

Real-life examples

Documents
├── Work
│   ├── Reports
│   └── Projects
└── Personal
    ├── Photos
    └── Videos

File systems form a tree of folders and files. Company structures similarly place leadership at the root, followed by managers and employees at lower levels.

Advantages of Trees

• Represent hierarchical information naturally
• Support efficient operations in balanced ordered trees
• Express parent-child relationships clearly
• Allow efficient insertion and deletion in suitable variants
• Power many databases and file systems

Limitations of Trees

• More complex than linear structures
• Unbalanced search trees can become slow
• Traversal and mutation require careful implementation
• Child references consume additional memory

Where are Trees used?

• Computer file systems
• Website navigation
• Organization charts
• HTML and XML documents
• Databases
• Search engines
• Artificial Intelligence
• Compilers

Tips for beginners

• Understand nodes and parent-child relationships
• Draw tree diagrams
• Learn DFS and BFS before advanced operations
• Compare trees with arrays and linked lists
• Practice small traversal problems

Key takeaways

• A tree is a non-linear hierarchical structure
• Every tree starts at a root
• Nodes connect through edges
• Leaves have no children
• DFS explores by branch and BFS explores by level
• Traversal takes O(n)
• Balanced ordered trees can support O(log n) search, insertion, and deletion