Chapter 11: Trees: Hierarchical Data

Introduction

Welcome back, aspiring data structure wizard! So far, we’ve mostly explored linear data structures like arrays, linked lists, stacks, and queues. These structures are fantastic for organizing data in a sequential fashion. But what if your data isn’t sequential? What if it has inherent relationships, like a family tree, an organizational chart, or the folders on your computer?

This is where Trees come into play! In this chapter, we’re going to dive into the exciting world of non-linear, hierarchical data structures. You’ll learn what a tree is, its fundamental terminology, why it’s so powerful for representing complex relationships, and we’ll even build a basic generic tree implementation using TypeScript. Get ready to branch out your understanding of data organization!

By the end of this chapter, you’ll have a solid grasp of tree fundamentals, paving the way for more specialized and powerful tree structures like Binary Trees, which we’ll explore next.

Core Concepts: Unpacking the Tree Structure

Imagine your computer’s file system. You have folders, and inside those folders, you can have more folders or files. This is a perfect real-world example of a tree structure!

A tree is a non-linear data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

The key characteristic is that it’s hierarchical and has no cycles. This means you can always trace a path from the root to any other node, and you’ll never loop back on yourself.

Key Tree Terminology

Before we start building, let’s get familiar with the language of trees. Understanding these terms is crucial for discussing and implementing tree-based algorithms.

• Node: The fundamental unit of a tree. Each node can store data and have connections to other nodes. Think of a file or a folder.
• Root Node: The topmost node in a tree. It’s the only node that has no parent. Every tree has exactly one root. In our file system analogy, this would be your C: drive or the root directory /.
• Edge: The link or connection between two nodes. It represents a relationship (e.g., a folder containing a file).
• Parent Node: A node that has one or more child nodes.
• Child Node: A node that has a parent node.
• Sibling Nodes: Nodes that share the same parent.
• Leaf Node: A node that has no children. These are at the “ends” of the branches. In a file system, these would be actual files, not folders.
• Path: A sequence of nodes and edges connecting one node to another.
• Depth of a Node: The number of edges from the root to that node. The root node has a depth of 0.
• Height of a Node: The number of edges on the longest path from the node to a leaf node. Leaf nodes have a height of 0.
• Height of a Tree: The height of its root node.
• Subtree: A tree formed by a node and all its descendants. Any node in a tree can be considered the root of a subtree.
• Degree of a Node: The number of children a node has.

Let’s visualize these concepts with a simple diagram.

In this diagram:

• A is the Root Node.
• B and C are Children of A, and also Siblings to each other.
• A is the Parent of B and C.
• D, E, F, G are Leaf Nodes (they have no children).
• The Depth of A is 0. The Depth of B is 1. The Depth of D is 2.
• The Height of D is 0. The Height of B is 1 (longest path to leaf D or E). The Height of the Tree (Node A) is 2.

Why Trees are So Useful

Trees are everywhere in computer science and real-world applications because they excel at representing hierarchical relationships and enabling efficient search, insertion, and deletion operations in many scenarios.

• File Systems: As discussed, folders and files form a tree.
• Organizational Charts: Companies often use tree structures to represent management hierarchies.
• Document Object Model (DOM): The structure of an HTML or XML document is a tree. Elements are nodes, and nested elements are children. Your web browser uses this heavily!
• Decision Trees: Used in machine learning for classification and regression tasks.
• Syntax Trees: Compilers use trees to represent the structure of programming code.
• Network Routing: Routers use tree-like structures to find the optimal path for data packets.

Trees offer a balance between the simplicity of linear structures and the complexity of graphs, providing structured ways to handle related data.

Step-by-Step Implementation: Building a Generic Tree

Let’s get our hands dirty and implement a basic generic tree in TypeScript. A “generic” tree means that each node can have any number of children, unlike specialized trees like binary trees where nodes have at most two children.

We’ll start by defining what a Node looks like, then create a Tree class to manage these nodes.

Step 1: Define the TreeNode Interface and Class

First, we need a way to represent an individual node within our tree. Each node will hold a piece of data and a list of its children.

Create a new file named tree.ts in your project.

// tree.ts

/**
 * Represents a single node in our generic tree.
 * Each node holds a value and a list of its children.
 */
interface ITreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

class TreeNode<T> implements ITreeNode<T> {
  value: T;
  children: TreeNode<T>[];

  constructor(value: T) {
    this.value = value;
    this.children = [];
  }

  /**
   * Adds a child node to the current node.
   * @param childNode The node to add as a child.
   */
  addChild(childNode: TreeNode<T>): void {
    this.children.push(childNode);
  }

  /**
   * Removes a child node from the current node based on its value.
   * Note: This only removes direct children.
   * @param value The value of the child node to remove.
   * @returns True if the child was found and removed, false otherwise.
   */
  removeChild(value: T): boolean {
    const initialLength = this.children.length;
    this.children = this.children.filter(child => child.value !== value);
    return this.children.length < initialLength; // True if an item was removed
  }
}

Explanation:

• ITreeNode<T> interface: This defines the shape of our tree node, making it clear what properties it must have. The <T> makes it a generic type, meaning our tree can store any type of data (numbers, strings, objects, etc.).
• TreeNode<T> class: This is the actual implementation of our node.
  • value: T;: Stores the data for this node.
  • children: TreeNode<T>[];: An array to hold references to its child nodes. This is what makes it a generic tree (can have many children).
  • constructor(value: T): Initializes a new node with a given value and an empty array of children.
  • addChild(childNode: TreeNode<T>): void: A simple method to add a new TreeNode to the children array.
  • removeChild(value: T): boolean: A utility method to remove a direct child by its value. It uses filter to create a new array without the specified child.

Step 2: Define the Tree Class

Now, let’s create the Tree class itself. This class will hold the root of our tree and provide methods to interact with the entire structure.

Add this code to the same tree.ts file, below the TreeNode class.

// tree.ts (continued)

/**
 * Represents a generic tree data structure.
 * It manages the root node and provides methods for adding, finding, and traversing nodes.
 */
class Tree<T> {
  root: TreeNode<T> | null; // The root of the tree, can be null if empty

  constructor() {
    this.root = null;
  }

  /**
   * Adds a new node to the tree.
   * If the tree is empty, the new node becomes the root.
   * Otherwise, it tries to find a parent node by its value and adds the new node as a child.
   * @param value The value of the new node to add.
   * @param parentValue The value of the parent node to attach the new node to. If null, it becomes the root.
   * @returns The newly added TreeNode, or null if the parent was not found.
   */
  add(value: T, parentValue: T | null = null): TreeNode<T> | null {
    const newNode = new TreeNode(value);

    // If tree is empty, make this the root
    if (this.root === null) {
      this.root = newNode;
      console.log(`Added root: ${String(value)}`);
      return newNode;
    }

    // If parentValue is provided, try to find the parent
    if (parentValue !== null) {
      const parentNode = this.find(parentValue); // We need a find method!
      if (parentNode) {
        parentNode.addChild(newNode);
        console.log(`Added ${String(value)} as child of ${String(parentValue)}`);
        return newNode;
      } else {
        console.warn(`Parent with value ${String(parentValue)} not found. Cannot add ${String(value)}.`);
        return null; // Parent not found
      }
    } else {
      // If parentValue is null but root already exists, we can't add another root
      console.warn(`Tree already has a root. Cannot add ${String(value)} without a parent.`);
      return null;
    }
  }

  /**
   * Finds a node in the tree by its value using a Depth-First Search (DFS) approach.
   * @param value The value of the node to find.
   * @returns The TreeNode if found, otherwise null.
   */
  find(value: T): TreeNode<T> | null {
    if (this.root === null) {
      return null;
    }

    // We'll use a stack for DFS traversal
    const stack: TreeNode<T>[] = [this.root];

    while (stack.length > 0) {
      const currentNode = stack.pop()!; // Pop the last node from the stack

      if (currentNode.value === value) {
        return currentNode; // Found the node!
      }

      // Add children to the stack to visit them later (in reverse order for DFS)
      for (let i = currentNode.children.length - 1; i >= 0; i--) {
        stack.push(currentNode.children[i]);
      }
    }

    return null; // Node not found after traversing the entire tree
  }

  /**
   * Performs a depth-first traversal of the tree, executing a callback function for each node.
   * @param callback A function to execute for each node, receiving the node's value and its depth.
   */
  traverseDFS(callback: (value: T, depth: number) => void): void {
    if (this.root === null) {
      return;
    }

    const stack: { node: TreeNode<T>; depth: number }[] = [{ node: this.root, depth: 0 }];

    while (stack.length > 0) {
      const { node: currentNode, depth } = stack.pop()!;
      callback(currentNode.value, depth);

      // Add children to the stack (again, reverse order for DFS processing)
      for (let i = currentNode.children.length - 1; i >= 0; i--) {
        stack.push({ node: currentNode.children[i], depth: depth + 1 });
      }
    }
  }

  /**
   * Performs a breadth-first traversal of the tree, executing a callback function for each node.
   * @param callback A function to execute for each node, receiving the node's value and its depth.
   */
  traverseBFS(callback: (value: T, depth: number) => void): void {
    if (this.root === null) {
      return;
    }

    // Use a queue for BFS traversal
    const queue: { node: TreeNode<T>; depth: number }[] = [{ node: this.root, depth: 0 }];

    while (queue.length > 0) {
      const { node: currentNode, depth } = queue.shift()!; // Dequeue the first node
      callback(currentNode.value, depth);

      // Enqueue all children
      for (const child of currentNode.children) {
        queue.push({ node: child, depth: depth + 1 });
      }
    }
  }
}

Explanation:

• root: TreeNode<T> | null;: The Tree class primarily holds a reference to its root node. If root is null, the tree is empty.
• constructor(): Initializes an empty tree.
• add(value: T, parentValue: T | null = null): TreeNode<T> | null:
  • This method is our primary way to build the tree.
  • It creates a newNode with the given value.
  • If this.root is null: The newNode becomes the tree’s root. This is the first node added to an empty tree.
  • If parentValue is provided: It calls this.find(parentValue) to locate the intended parent. If found, newNode is added as a child to that parent using parentNode.addChild(newNode).
  • Important Note: If a parentValue is null but a root already exists, it prevents adding a second root, which is invalid for a single-rooted tree.
• find(value: T): TreeNode<T> | null:
  • This method implements a Depth-First Search (DFS) to find a node by its value.
  • It uses a stack (a simple array in TypeScript, leveraging push and pop). DFS explores as far as possible along each branch before backtracking.
  • It starts with the root on the stack. In each iteration, it pops a node, checks its value, and then pushes its children onto the stack (in reverse order so the left-most child is processed first in the next iteration).
• traverseDFS(callback: (value: T, depth: number) => void): void:
  • Similar to find, this uses DFS to visit every node in the tree.
  • Instead of returning a node, it executes a callback function for each node, passing its value and its depth (distance from the root). This is useful for printing or processing nodes in a specific order.
• traverseBFS(callback: (value: T, depth: number) => void): void:
  • This method implements a Breadth-First Search (BFS), which explores the tree level by level.
  • It uses a queue (a simple array in TypeScript, leveraging push and shift). BFS visits all nodes at the current depth before moving to the next depth level.
  • It starts with the root in the queue. In each iteration, it shifts a node, executes the callback, and then pushes all of its children into the queue.

Step 3: Using Our Generic Tree

Let’s test our Tree implementation!

Create a new file called app.ts (or index.ts) and import our Tree and TreeNode classes.

// app.ts

import { Tree, TreeNode } from './tree'; // Assuming tree.ts is in the same directory

console.log("--- Building a Sample Tree ---");
const organizationTree = new Tree<string>();

// Add the CEO (root)
organizationTree.add("CEO"); // No parentValue, becomes root

// Add direct reports to CEO
organizationTree.add("CTO", "CEO");
organizationTree.add("CFO", "CEO");
organizationTree.add("VP Marketing", "CEO");

// Add reports to CTO
organizationTree.add("Lead Engineer A", "CTO");
organizationTree.add("Lead Engineer B", "CTO");

// Add reports to CFO
organizationTree.add("Accounting Manager", "CFO");

// Try to add to a non-existent parent
organizationTree.add("Junior Developer", "Lead Engineer C"); // This should fail

console.log("\n--- Finding Nodes ---");
const ctoNode = organizationTree.find("CTO");
if (ctoNode) {
  console.log(`Found CTO node: ${ctoNode.value}`);
  console.log(`CTO's children: ${ctoNode.children.map(c => c.value).join(', ')}`);
} else {
  console.log("CTO node not found.");
}

const juniorDevNode = organizationTree.find("Junior Developer");
if (juniorDevNode) {
  console.log(`Found Junior Developer node: ${juniorDevNode.value}`);
} else {
  console.log("Junior Developer node not found (as expected).");
}

console.log("\n--- Depth-First Traversal (DFS) ---");
organizationTree.traverseDFS((value, depth) => {
  console.log(`${'  '.repeat(depth)}- ${value}`);
});

console.log("\n--- Breadth-First Traversal (BFS) ---");
organizationTree.traverseBFS((value, depth) => {
  console.log(`${'  '.repeat(depth)}- ${value}`);
});

console.log("\n--- Removing a Node (and its subtree) ---");
// To remove a node from the tree, we need to find its parent and then remove it from the parent's children array.
// Let's remove 'Lead Engineer B'. Its parent is 'CTO'.
const ctoParent = organizationTree.find("CTO");
if (ctoParent) {
    console.log(`Before removal, CTO's children: ${ctoParent.children.map(c => c.value).join(', ')}`);
    const removed = ctoParent.removeChild("Lead Engineer B");
    if (removed) {
        console.log("Removed 'Lead Engineer B' successfully.");
    } else {
        console.log("Failed to remove 'Lead Engineer B'.");
    }
    console.log(`After removal, CTO's children: ${ctoParent.children.map(c => c.value).join(', ')}`);
}

console.log("\n--- DFS After Removal ---");
organizationTree.traverseDFS((value, depth) => {
    console.log(`${'  '.repeat(depth)}- ${value}`);
});

To run this code:

1. Make sure you have Node.js (v24.13.0 LTS or v25.6.1 Current as of 2026-02-16) and TypeScript installed.
2. Compile the TypeScript files: npx tsc tree.ts app.ts
3. Run the compiled JavaScript: node app.js

You should see output demonstrating the tree being built, nodes being found, and the different traversal orders (DFS and BFS). Notice how DFS goes deep first, while BFS goes wide first.

Mini-Challenge: Counting Nodes

Now it’s your turn!

Challenge: Add a new method to the Tree class called countNodes(): number that returns the total number of nodes in the tree.

Hint: You can adapt one of the traversal methods (DFS or BFS) to visit every node and simply increment a counter.

What to observe/learn: This exercise reinforces your understanding of tree traversal and how to apply it to extract information from the tree. It also highlights that even simple operations often require traversing the entire structure.

// Add this method inside your Tree class
// ...
// class Tree<T> {
//   // ... existing code ...

//   /**
//    * Counts the total number of nodes in the tree.
//    * @returns The total count of nodes.
//    */
//   countNodes(): number {
//     // Your code here!
//     // Remember to handle an empty tree gracefully.
//     // Use a traversal method (DFS or BFS) to visit all nodes and count them.
//   }
// }

Once you’ve implemented it, add a call to console.log(organizationTree.countNodes()); in app.ts to test it.

Common Pitfalls & Troubleshooting

Working with tree structures can introduce some unique challenges:

1. Forgetting to Handle Null Roots: Always check if this.root is null at the beginning of any method that interacts with the tree. An empty tree needs special handling. If you try to access this.root.children on a null root, you’ll get a TypeError (or Cannot read properties of null).
2. Incorrect Parent-Child References: When adding or removing nodes, it’s easy to mismanage the children array. Ensure you’re adding children to the correct parent and that removal correctly updates the parent’s children list. A common mistake is adding a node but forgetting to link it to its parent, making it an unreachable “orphan.”
3. Infinite Loops in Traversal (Less common in strict trees, but good to know): While our generic tree guarantees no cycles, if you were dealing with a more general graph structure or a poorly implemented tree where a child somehow pointed back to an ancestor, a simple traversal without tracking visited nodes could lead to an infinite loop. Always be mindful of cycles in graph-like structures.
4. Performance of find and add in Generic Trees: Our find and add methods (which rely on find) iterate through potentially all nodes in the worst case (O(N) time complexity, where N is the number of nodes). For small trees, this is fine, but for very large trees, this can be inefficient. This is why specialized trees like Binary Search Trees (which we’ll cover next!) are designed for much faster operations.

Summary

Phew! You’ve just taken a significant step into non-linear data structures. Let’s recap what we’ve learned in this chapter:

• Trees are hierarchical data structures used to represent relationships where data branches out.
• We distinguished between key tree terminology: root, node, parent, child, sibling, leaf, edge, path, depth, height, and subtree.
• We saw how trees are used in real-world applications like file systems, the DOM, and organizational charts.
• You implemented a generic TreeNode and Tree class in TypeScript, capable of storing any data type.
• You learned to add nodes and find nodes within the tree.
• You explored two fundamental tree traversal algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS), understanding their different visitation orders.
• You tackled a mini-challenge to count nodes, solidifying your understanding of traversal.
• We discussed common pitfalls like null root checks and managing references.

You now have a foundational understanding of trees. In the next chapter, we’ll build upon this by diving into a very common and optimized type of tree: the Binary Tree. Get ready for even more structured data adventures!

References

• Node.js Official Website
• TypeScript Handbook
• MDN Web Docs: Data structures - Trees
• GeeksforGeeks: Tree Data Structure
• freeCodeCamp: The Ultimate Guide to JavaScript Algorithms: Tree Data Structure

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.