Trees: DFS, BFS, and the org chart

import csv
from collections import defaultdict, deque

emps = list(csv.DictReader(open("employees.csv")))
name = {e["emp_id"]: e["name"] for e in emps}
children = defaultdict(list)
root = None
for e in emps:
    if e["manager_id"]:
        children[e["manager_id"]].append(e["emp_id"])
    else:
        root = e["emp_id"]

def dfs(node, depth=0):               # depth-first: go deep, then back
    print("  " * depth + name[node])
    for c in children[node]:
        dfs(c, depth + 1)

def bfs(start):                        # breadth-first: level by level
    levels, q = [], deque([(start, 0)])
    while q:
        node, d = q.popleft()
        if d == len(levels):
            levels.append([])
        levels[d].append(name[node])
        q.extend((c, d + 1) for c in children[node])
    return levels

dfs(root)
print(bfs(root))

Anita
  Rahul
    Priya
    Karan
  Neha
    Arjun
    Ishita
  Dev
    Tara
[['Anita'], ['Rahul', 'Neha', 'Dev'], ['Priya', 'Karan', 'Arjun', 'Ishita', 'Tara']]

from dataclasses import dataclass

@dataclass
class T:
    val: int
    left: "T | None" = None
    right: "T | None" = None

def insert(node, v):                   # binary search tree
    if node is None:
        return T(v)
    if v < node.val:
        node.left = insert(node.left, v)
    else:
        node.right = insert(node.right, v)
    return node

def inorder(n):                        # left, root, right = sorted
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

def height(n):
    return 1 + max(height(n.left), height(n.right)) if n else 0

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
chain = None
for v in [10, 20, 30, 40, 50, 60, 70]:  # sorted: a line
    chain = insert(chain, v)
print(inorder(root), height(root), height(chain))

[20, 30, 40, 50, 60, 70, 80] 3 7