# Binary Tree — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/binary-tree

> Each node has up to two children; traversals visit every node once.

## Shape & terms

```
        1
       / \
      2   3
     / \
    4   5
```

Root at top, leaves at bottom. **Height** is the longest root-to-leaf path. A balanced tree has height `~log n`; a degenerate one is a linked list with height `n`.

## The four traversals

Depth-first: pre/in/post-order differ only by *when* you visit the node vs. recurse. Breadth-first uses a queue, level by level.

```python
def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)     # visit between children
    inorder(node.right, out)

from collections import deque
def bfs(root):
    q, out = deque([root]), []
    while q:
        n = q.popleft()
        out.append(n.val)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out
```

## Org chart

The CEO is the root; each manager has reports beneath them. To brief everyone you can go department-deep (DFS) or floor-by-floor (BFS).

## Interview pattern

Most tree problems are one recursive function returning info from children (height, sum, is-balanced, LCA). Think: "what do I need from left and right to answer for this node?"