Skip to main content

​
Tree

A hierarchical data structure consisting of nodes where each node can have multiple children. Unlike binary trees, nodes are not limited to two children.

​
Overview

General trees represent hierarchical relationships where each node can have any number of children. This structure is fundamental for representing file systems, organizational charts, and nested data.

​
Implementation

​
Node Structure

class Node<T = number> {
  value: T;
  children: Node<T>[] = [];

  constructor(value: T) {
    this.value = value;
  }
}
Reference: node.ts:1-9

​
Class Definition

class Tree<T> {
  root: Node<T> | null = null;

  constructor(root: T) {
    this.root = new Node(root);
  }
  
  // ... methods
}
Reference: tree.ts:3-8

​
API Reference

​
insert(parent: T, node: T): boolean

Inserts a new node as a child of the specified parent node. 
const tree = new Tree<number>(1);
tree.insert(1, 2); // Add 2 as child of 1
tree.insert(1, 3); // Add 3 as child of 1
tree.insert(2, 4); // Add 4 as child of 2

// Tree structure:
//       1
//      / \
//     2   3
//    /
//   4
Parameters:
  • parent: Value of the parent node
  • node: Value to insert as a new child
Returns: true if insertion succeeded, false if parent not found Complexity: O(n) - must search for parent node Reference: tree.ts:23-38

​
search(value: T): Node<T> | undefined

Searches for a node with the specified value. 
const tree = new Tree<number>(1);
tree.insert(1, 2);
tree.insert(1, 3);

const node = tree.search(2);
console.log(node?.value); // 2
console.log(node?.children); // []
Parameters:
  • value: The value to search for
Returns: The node if found, undefined otherwise Complexity: O(n) - may need to traverse entire tree Reference: tree.ts:40-50

​
Internal Methods

​
#traverse(node, callback)

Private method for tree traversal using depth-first search. 
#traverse(node: Node<T> | null, callback: (node: Node<T>) => void) {
  if (!node) {
    return;
  }

  callback(node);

  for (const child of node.children) {
    callback(child);
    this.#traverse(child, callback);
  }
}
Traversal Order: Pre-order (parent, then children) Reference: tree.ts:10-21

​
Usage Examples

​
Building a File System

class FileSystem {
  private tree: Tree<string>;
  
  constructor(rootDir: string) {
    this.tree = new Tree(rootDir);
  }
  
  createDirectory(parent: string, dirName: string) {
    return this.tree.insert(parent, dirName);
  }
  
  findDirectory(dirName: string) {
    return this.tree.search(dirName);
  }
}

const fs = new FileSystem('/');
fs.createDirectory('/', 'home');
fs.createDirectory('/', 'etc');
fs.createDirectory('/home', 'user');
fs.createDirectory('/home/user', 'documents');

// File system structure:
//        /
//       / \
//    home  etc
//     |
//    user
//     |
// documents

​
Organization Chart

interface Employee {
  id: number;
  name: string;
  role: string;
}

const orgChart = new Tree<Employee>({
  id: 1,
  name: 'CEO',
  role: 'Chief Executive'
});

orgChart.insert(
  { id: 1, name: 'CEO', role: 'Chief Executive' },
  { id: 2, name: 'CTO', role: 'Technology' }
);

orgChart.insert(
  { id: 1, name: 'CEO', role: 'Chief Executive' },
  { id: 3, name: 'CFO', role: 'Finance' }
);

interface MenuItem {
  id: string;
  label: string;
  url?: string;
}

const menu = new Tree<MenuItem>({
  id: 'root',
  label: 'Main Menu'
});

menu.insert(
  { id: 'root', label: 'Main Menu' },
  { id: 'products', label: 'Products' }
);

menu.insert(
  { id: 'products', label: 'Products' },
  { id: 'laptops', label: 'Laptops', url: '/products/laptops' }
);

menu.insert(
  { id: 'products', label: 'Products' },
  { id: 'phones', label: 'Phones', url: '/products/phones' }
);

​
Traversal Patterns

​
Depth-First Search (DFS)

The implementation uses DFS for traversal: 
function printTree<T>(tree: Tree<T>) {
  const values: T[] = [];
  
  tree.#traverse(tree.root, (node) => {
    values.push(node.value);
  });
  
  console.log(values);
}

​
Custom Traversal

// Count total nodes
function countNodes<T>(tree: Tree<T>): number {
  let count = 0;
  
  tree.#traverse(tree.root, () => {
    count++;
  });
  
  return count;
}

// Find maximum depth
function maxDepth<T>(node: Node<T> | null): number {
  if (!node || node.children.length === 0) {
    return 0;
  }
  
  let max = 0;
  for (const child of node.children) {
    max = Math.max(max, maxDepth(child));
  }
  
  return max + 1;
}

​
Complexity Summary

OperationTime ComplexitySpace Complexity
insertO(n)O(1)
searchO(n)O(h)*
traverseO(n)O(h)*
*h = height of tree (due to recursion call stack)

​
Tree vs Other Structures

FeatureGeneral TreeBinary TreeN-ary Tree
Children per nodeUnlimitedMax 2Max N
StorageDynamic arrayTwo pointersFixed array
Use caseHierarchiesSearch treesTries, B-trees
MemoryVariableFixedFixed

​
Key Characteristics

Advantages:
  • Natural representation of hierarchies
  • Flexible number of children
  • Intuitive for nested data
  • Easy to implement recursive algorithms
Limitations:
  • No guaranteed balance
  • O(n) search time
  • Not optimized for searching
  • Memory overhead for children array

​
Common Operations

​
Finding Leaf Nodes

function findLeaves<T>(tree: Tree<T>): Node<T>[] {
  const leaves: Node<T>[] = [];
  
  function traverse(node: Node<T> | null) {
    if (!node) return;
    
    if (node.children.length === 0) {
      leaves.push(node);
    }
    
    for (const child of node.children) {
      traverse(child);
    }
  }
  
  traverse(tree.root);
  return leaves;
}

​
Finding Height

function height<T>(node: Node<T> | null): number {
  if (!node) return -1;
  
  let maxChildHeight = -1;
  for (const child of node.children) {
    maxChildHeight = Math.max(maxChildHeight, height(child));
  }
  
  return maxChildHeight + 1;
}

​
Level-Order Traversal

function levelOrder<T>(tree: Tree<T>): T[][] {
  if (!tree.root) return [];
  
  const result: T[][] = [];
  const queue: Node<T>[] = [tree.root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: T[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.value);
      queue.push(...node.children);
    }
    
    result.push(currentLevel);
  }
  
  return result;
}

​
When to Use a General Tree

Directories can contain multiple files and subdirectories.
HTML elements can have any number of child elements.
Employees can manage multiple direct reports.
Code expressions can have varying numbers of operands.
For optimized searching, consider using specialized tree structures:

Binary Search Tree

Optimized tree for searching

Graph

Generalization allowing cycles

Build docs developers (and LLMs) love

Get started for freeTalk to us