Binary Tree Intro

A tree is a hierarchical structure.

Real examples:

• file system folders
• HTML DOM
• organization charts

Tree vocabulary

• root: top node
• child: below a node
• leaf: node with no children

Simple binary tree node

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Build a small tree

root = Node(1, Node(2), Node(3))

DFS traversal (in-order)

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

inorder(root)  # 2,1,3

BFS traversal (level order)

from collections import deque

def bfs(root):
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

bfs(root)  # 1,2,3

Graph: tree structure

flowchart TD
  A[1] --> B[2]
  A --> C[3]

Remember

• Trees model hierarchy
• DFS uses recursion or stack
• BFS uses queue