Binary Trees

Question¶

Define binary trees and provide an implementation in Python.

Definition¶

Each node has at most two children, usually left and right.

Example¶

    1
   / \
  2   3
 /
4

Implementation¶

from dataclasses import dataclass

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

root = BinNode(1, BinNode(2, BinNode(4)), BinNode(3))

Key trick¶

Binary trees are ideal for recursive divide-and-conquer.

Trap¶

Inorder meaning only makes sense naturally for binary trees.

Use¶

Ordered trees, expression trees, BSTs, heaps.