Binary Trees — Nodes, Edges, and Traversals
treesbinary-treesdata-structuresbeginnerfree
The foundation of tree-based data structures — what binary trees are, how to traverse them, and why they matter.
What Is a Binary Tree?
A binary tree is a hierarchical data structure where each node has at most two children, called the left child and right child. The topmost node is the root. Nodes with no children are leaves.
Trees model naturally hierarchical data: file systems, HTML DOM, org charts, decision trees. They are the foundation for BSTs, heaps, tries, and segment trees.
Tree Traversals
There are three main depth-first traversals:
- Inorder (left, root, right) — on a BST, this gives sorted order
- Preorder (root, left, right) — useful for copying a tree or prefix expressions
- Postorder (left, right, root) — useful for deleting a tree or postfix expressions
And one breadth-first traversal:
- Level-order — visit nodes level by level using a queue (BFS on a tree)
python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder(node):
if node:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
def preorder(node):
if node:
print(node.value, end=" ")
preorder(node.left)
preorder(node.right)
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.value, end=" ")
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
print("Inorder: ", end="")
inorder(root)
print("\nPreorder: ", end="")
preorder(root)
print("\nPostorder:", end=" ")
postorder(root)
print()Binary tree traversal methods
| Traversal | Order | Use Case |
|---|---|---|
| Inorder | Left, Root, Right | BST sorted output |
| Preorder | Root, Left, Right | Copy/serialize a tree |
| Postorder | Left, Right, Root | Delete a tree, evaluate expressions |
| Level-order | BFS with queue | Shortest path in unweighted tree |
Key Takeaways
- Binary trees: each node has at most 2 children. Root at top, leaves at bottom.
- Three DFS traversals: inorder, preorder, postorder. Plus level-order (BFS).
- All traversals are O(n) time and O(h) space where h is the tree height.
- Trees are the foundation for BSTs, heaps, tries, segment trees, and expression trees.