Binary Tree

Back to Index

Each node has at most two children (left and right). The algorithmic patterns are in Trees; this note covers the structural properties and representations.

Node Definition

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Types

• Binary Tree: at most 2 children, no ordering constraint
• BST (Binary Search Tree): left < node < right for all nodes
• Complete Binary Tree: all levels full except last, last filled left to right
• Perfect Binary Tree: all internal nodes have 2 children, all leaves at same level
• Balanced Binary Tree: height of left and right subtrees differ by at most 1

Key Properties

Type	Height	Notes
Balanced	O(log n)	AVL, Red-Black trees guarantee this
Skewed (worst)	O(n)	Degenerates to linked list
Perfect	log(n+1) - 1	Exactly 2^h - 1 nodes

Representations

• Linked nodes: standard for most problems
• Array (heap-style): for complete binary trees — node at index i has children at 2i+1 and 2i+2, parent at (i-1)//2
• Level-order list with nulls: LeetCode input format, e.g. [1, 2, 3, null, null, 4, 5]

Patterns That Use This

Trees — traversals, path problems, LCA BFS — level-order traversal DFS — recursive exploration Dynamic Programming — tree DP (bottom-up computation)

---

Problems Using This Data Structure