{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "title",
   "metadata": {},
   "source": [
    "# Trees & Graphs\n",
    "\n",
    "Trees and graphs organize relationships. Trees model hierarchy; graphs model general connections.\n",
    "\n",
    "```text\n",
    "Outline\n",
    "\n",
    "Trees\n",
    "  o Root, children, leaves\n",
    "  o Recursive traversal\n",
    "Graphs\n",
    "  o Nodes and edges\n",
    "  o Adjacency lists\n",
    "Graph Traversal\n",
    "  o Breadth-first search\n",
    "  o Depth-first search\n",
    "Summary\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "trees",
   "metadata": {},
   "source": [
    "## Trees\n",
    "\n",
    "A **tree** is a linked structure with a root and branches. Each node can have children. A node with no children is called a leaf.\n",
    "\n",
    "Trees are useful for hierarchical data such as folders, organization charts, HTML documents, decision trees, and expression trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "tree-code",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.children = []\n",
    "\n",
    "    def add_child(self, child):\n",
    "        self.children.append(child)\n",
    "\n",
    "\n",
    "root = TreeNode(\"company\")\n",
    "analytics = TreeNode(\"analytics\")\n",
    "operations = TreeNode(\"operations\")\n",
    "\n",
    "root.add_child(analytics)\n",
    "root.add_child(operations)\n",
    "analytics.add_child(TreeNode(\"alice\"))\n",
    "analytics.add_child(TreeNode(\"bob\"))\n",
    "operations.add_child(TreeNode(\"charlie\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "tree-print",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_tree(node, level=0):\n",
    "    indent = \"  \" * level\n",
    "    print(indent + str(node.value))\n",
    "    for child in node.children:\n",
    "        print_tree(child, level + 1)\n",
    "\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-tree",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Add a Tree Node\n",
    "# Add a new employee named dana under operations.\n",
    "# Then print the tree again.\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-tree",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "operations.add_child(TreeNode(\"dana\"))\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "graphs",
   "metadata": {},
   "source": [
    "## Graphs\n",
    "\n",
    "A **graph** stores relationships between items. The items are nodes. The relationships are edges.\n",
    "\n",
    "A common Python representation is an adjacency list: a dictionary where each key maps to a list of neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "graph-code",
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = {\n",
    "    \"alice\": [\"bob\", \"charlie\"],\n",
    "    \"bob\": [\"alice\", \"dana\"],\n",
    "    \"charlie\": [\"alice\", \"dana\"],\n",
    "    \"dana\": [\"bob\", \"charlie\"],\n",
    "}\n",
    "\n",
    "print(graph[\"alice\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-graph",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Add a Graph Edge\n",
    "# Add a new person named erin who is connected to dana.\n",
    "# Update both adjacency lists so the relationship works both ways.\n",
    "# Then print graph[\"dana\"].\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-graph",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "graph[\"erin\"] = [\"dana\"]\n",
    "graph[\"dana\"].append(\"erin\")\n",
    "\n",
    "print(graph[\"dana\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "traversal",
   "metadata": {},
   "source": [
    "## Graph Traversal\n",
    "\n",
    "A traversal visits nodes systematically.\n",
    "\n",
    "- **Breadth-first search** uses a queue and explores nearby nodes first.\n",
    "- **Depth-first search** uses a stack or recursion and follows one path before backing up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "traversal-code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "\n",
    "def breadth_first_search(graph, start):\n",
    "    visited = set()\n",
    "    order = []\n",
    "    queue = deque([start])\n",
    "\n",
    "    while queue:\n",
    "        node = queue.popleft()\n",
    "        if node in visited:\n",
    "            continue\n",
    "\n",
    "        visited.add(node)\n",
    "        order.append(node)\n",
    "\n",
    "        for neighbor in graph.get(node, []):\n",
    "            if neighbor not in visited:\n",
    "                queue.append(neighbor)\n",
    "\n",
    "    return order\n",
    "\n",
    "\n",
    "print(breadth_first_search(graph, \"alice\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-traversal",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Stop at a Target\n",
    "# Modify breadth_first_search so it accepts a target node.\n",
    "# The function should return the visited order once the target is found.\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-traversal",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "def bfs_until(graph, start, target):\n",
    "    visited = set()\n",
    "    order = []\n",
    "    queue = deque([start])\n",
    "\n",
    "    while queue:\n",
    "        node = queue.popleft()\n",
    "        if node in visited:\n",
    "            continue\n",
    "\n",
    "        visited.add(node)\n",
    "        order.append(node)\n",
    "\n",
    "        if node == target:\n",
    "            return order\n",
    "\n",
    "        for neighbor in graph.get(node, []):\n",
    "            if neighbor not in visited:\n",
    "                queue.append(neighbor)\n",
    "\n",
    "    return order\n",
    "\n",
    "\n",
    "print(bfs_until(graph, \"alice\", \"erin\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "summary",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "Trees model hierarchy. Graphs model general relationships. Traversal algorithms make these structures useful because they provide repeatable ways to visit connected data."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}