Binary Tree
DSA · Trees
Theory
A binary tree is a tree in which every node has at most two children, called left and right. Special shapes include full trees (every node has 0 or 2 children), complete trees (every level filled except possibly the last, filled left to right) and perfect trees (all levels full). A complete binary tree can be stored in an array, which is how heaps are implemented.
Why we use it
The two-child structure keeps algorithms simple and is the basis for binary search trees, heaps and expression trees.
When to use it
Use binary trees for BSTs, heaps, expression parsing, Huffman coding and many interview problems.
How it works
- Root
- Each node has at most 2 children: left and right
- Node is None? Yes: Stop (empty subtree). No: Process node, then left and right.
- Done
Syntax
class Node:
def __init__(self, v): self.val = v; self.left = None; self.right = None
Array form (complete tree): children of i at 2i+1 and 2i+2, parent at (i-1)//2Example
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
def count_nodes(n):
return 0 if n is None else 1 + count_nodes(n.left) + count_nodes(n.right)
def max_depth(n):
return 0 if n is None else 1 + max(max_depth(n.left), max_depth(n.right))
def tree_sum(n):
return 0 if n is None else n.val + tree_sum(n.left) + tree_sum(n.right)
print("Nodes:", count_nodes(root), "| Depth:", max_depth(root), "| Sum:", tree_sum(root))Key points
- At most two children per node
- Full, complete and perfect are special shapes
- Complete trees fit neatly in arrays
- Recursion on left and right solves most problems