Trees and Graphs: Hierarchical Data Structures

class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree<T> {
  root: TreeNode<T> | null = null;

  insert(value: T) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return;
    }
    this.insertNode(this.root, node);
  }

  private insertNode(parent: TreeNode<T>, node: TreeNode<T>) {
    if (node.value < parent.value) {
      if (!parent.left) {
        parent.left = node;
      } else {
        this.insertNode(parent.left, node);
      }
    } else {
      if (!parent.right) {
        parent.right = node;
      } else {
        this.insertNode(parent.right, node);
      }
    }
  }

  inorderTraversal(node: TreeNode<T> | null = this.root): T[] {
    if (!node) return [];
    return [
      ...this.inorderTraversal(node.left),
      node.value,
      ...this.inorderTraversal(node.right)
    ];
  }
}

class Graph<T> {
  private adjacencyList: Map<T, Set<T>> = new Map();

  addVertex(vertex: T) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, new Set());
    }
  }

  addEdge(vertex1: T, vertex2: T) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    this.adjacencyList.get(vertex1)!.add(vertex2);
    this.adjacencyList.get(vertex2)!.add(vertex1);
  }

  bfs(start: T): T[] {
    const visited = new Set<T>();
    const queue: T[] = [start];
    const result: T[] = [];

    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift()!;
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return result;
  }
}