Intermediate·2 min read
Binary Trees
Understand tree structures and master all traversal methods.
Binary Trees
A binary tree is a hierarchical structure where each node has at most two children.
``
1 ← Root (level 0)
/ \
2 3 ← Level 1
/ \ / \
4 5 6 7 ← Level 2 (leaves)
``Key Terminology
- Root: Top node (1)
- Leaf: Node with no children (4, 5, 6, 7)
- Height: Longest path from root to leaf = 2
- Depth: Distance from root to a node
- Subtree: A tree rooted at any node
Traversals
In-order (Left, Root, Right): 4, 2, 5, 1, 6, 3, 7- BST in-order gives sorted order
- Useful for copying/serializing a tree
- Useful for deleting a tree safely
- Process level by level using a queue
Memory Representation
- Linked: Each node has left/right pointers (most common)
- Sequential (Array): For complete binary trees
- Right child: 2i + 2
- Parent: (i - 1) / 2
Code Example
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_sample_tree():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
return root
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
def level_order(root):
if not root:
return []
from collections import deque
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
tree = build_sample_tree()
print("In-order: ", inorder(tree))
print("Pre-order: ", preorder(tree))
print("Post-order:", postorder(tree))
print("Level-order:", level_order(tree))Practice Problems
- 01Find the height of a binary tree recursively
- 02Check if two binary trees are identical
- 03Print all root-to-leaf paths in a binary tree