Binary Trees — Traversals & Operations Guide
In this tutorial, you'll learn about Binary Trees. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A Binary Tree is a hierarchical data structure where each node has at most two children — left and right. Unlike arrays and linked lists, trees represent non-linear, hierarchical relationships.
What You'll Learn
You will learn Binary Tree terminology, tree traversal algorithms (DFS and BFS), how to compute tree height and diameter, and how to implement these in Python and JavaScript.
Why It Matters
Binary trees are the foundation for binary search trees, heaps, expression trees, and syntax trees in compilers. Understanding tree traversal is essential for any complex data manipulation.
Real-World Use
The DOM (Document Object Model) in Doda Browser is a tree structure. When the browser renders a web page, it traverses the DOM tree to compute styles, layout, and paint elements. The rendering engine uses depth-first traversal for style computation.
Binary Tree Terminology
graph TD
R[Root: 1] --> L[Left: 2]
R --> RI[Right: 3]
L --> LL[Left: 4]
L --> LR[Right: 5]
RI --> RIL[Left: 6]
RI --> RIR[Right: 7]
style R fill:#4a90d9,stroke:#333,color:#fff
- Root: The topmost node (1)
- Leaf: A node with no children (4, 5, 6, 7)
- Parent: A node that has children (1 is parent of 2, 3)
- Child: A node below its parent (2, 3 are children of 1)
- Height: Longest path from root to leaf (3 edges here)
- Depth: Number of edges from root to node
Binary Tree Node
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
DFS Traversals
Depth-First Search explores as far as possible along each branch before Backtracking.
Inorder (Left, Root, Right)
def inorder(node):
if node:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
inorder(root) # 4 2 5 1 6 3 7
Preorder (Root, Left, Right)
def preorder(node):
if node:
print(node.value, end=" ")
preorder(node.left)
preorder(node.right)
preorder(root) # 1 2 4 5 3 6 7
Postorder (Left, Right, Root)
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.value, end=" ")
postorder(root) # 4 5 2 6 7 3 1
function inorder(node) {
if (!node) return;
inorder(node.left);
process.stdout.write(node.value + " ");
inorder(node.right);
}
function preorder(node) {
if (!node) return;
process.stdout.write(node.value + " ");
preorder(node.left);
preorder(node.right);
}
function postorder(node) {
if (!node) return;
postorder(node.left);
postorder(node.right);
process.stdout.write(node.value + " ");
}
// Build and traverse
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
inorder(root); // 4 2 5 1 6 3 7
postorder(root); // 4 5 2 6 7 3 1
BFS (Level-Order) Traversal
BFS visits nodes level by level, from left to right.
from collections import deque
def level_order(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.value, end=" ")
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level_order(root) # 1 2 3 4 5 6 7
function levelOrder(root) {
if (!root) return;
let q = [root];
while (q.length) {
let node = q.shift();
process.stdout.write(node.value + " ");
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
Tree Height and Diameter
Height
def tree_height(node):
if not node:
return 0
return 1 + max(tree_height(node.left), tree_height(node.right))
print("Height:", tree_height(root)) # 2 (edges from root to deepest leaf)
Diameter (Longest Path)
The diameter is the longest path between any two nodes, measured in edges.
def tree_diameter(root):
diameter = 0
def height(node):
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter
print("Diameter:", tree_diameter(root)) # 4 (path: 4-2-1-3-7 or 4-2-1-3-6)
Expected output:
Height: 2
Diameter: 4
Common Pitfalls
1. Null Node Checks
Always check if node before accessing node.left or node.right. Null pointer dereference is the most common tree bug.
2. Infinite Recursion
Ensure each recursive call moves toward a base case (null node). Forgetting to update the node parameter causes stack overflow.
3. Confusing Traversal Orders
Inorder gives sorted output for BSTs. Preorder creates a copy. Postorder deletes children before parent. Choose the right order for your use case.
4. Not Using Iterative Approaches for Deep Trees
Deep recursive traversals can overflow the call stack. Use iterative traversal with an explicit stack for production code.
5. Mutable Default Arguments in Recursion
Using memo={} as a default argument persists across calls. Use None and initialize inside the function.
Iterative DFS Traversal
def inorder_iterative(root):
stack = []
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
print(curr.value, end=" ")
curr = curr.right
inorder_iterative(root) # 4 2 5 1 6 3 7
Practice Questions
1. Check if two binary trees are identical.
def is_identical(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.value == q.value and
is_identical(p.left, q.left) and
is_identical(p.right, q.right))
2. Find the maximum depth (height) of a Binary Tree.
3. Determine if a Binary Tree is symmetric (mirror of itself).
4. Challenge: Serialize and deserialize a Binary Tree — convert it to a string and back. Used in Doda Browser's session restoration to save and restore open tab structures.
5. Real-world task: DodaZIP's file explorer displays directory contents as a tree. Write a function that takes a flat list of file paths and builds a nested tree structure, then prints it using level-order traversal.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro