Binary Tree Explanation (with Python Implementation)
Definition
A binary tree is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child.
Each node contains:
• Data (the value stored in the node)
• References (pointers) to its left and right child nodes
Formally, a binary tree is either:
1. Empty, or
2. Consists of a root node and two disjoint binary trees called the left and right
subtrees.
Structure of a Node
In Python, each node can be represented as an object of a class that contains three
attributes — data, left, and right.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
Creating a Binary Tree
A binary tree can be constructed by linking nodes together.
# Example tree:
# 10
# / \
# 5 15
# / \ \
# 2 7 20
root = Node(10)
[Link] = Node(5)
[Link] = Node(15)
[Link] = Node(2)
[Link] = Node(7)
[Link] = Node(20)
Tree Traversals
Traversal refers to the process of visiting all nodes of a tree in a specific order.
1. Inorder Traversal (Left → Root → Right)
def inorder(node):
if node:
inorder([Link])
print([Link], end=' ')
inorder([Link])
Output for the above tree:
2 5 7 10 15 20
2. Preorder Traversal (Root → Left → Right)
def preorder(node):
if node:
print([Link], end=' ')
preorder([Link])
preorder([Link])
Output:
10 5 2 7 15 20
3. Postorder Traversal (Left → Right → Root)
def postorder(node):
if node:
postorder([Link])
postorder([Link])
print([Link], end=' ')
Output:
2 7 5 20 15 10
4. Level-order Traversal (Breadth-first)
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = [Link]()
print([Link], end=' ')
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
Output:
10 5 15 2 7 20
Binary Search Tree (BST) Insertion Example
A Binary Search Tree is a special binary tree where:
• Left child < Root
• Right child > Root
Here’s how insertion works:
def insert(root, data):
if root is None:
return Node(data)
if data < [Link]:
[Link] = insert([Link], data)
else:
[Link] = insert([Link], data)
return root
Example usage:
root = None
for value in [10, 5, 15, 2, 7, 20]:
root = insert(root, value)
inorder(root) # Prints sorted order: 2 5 7 10 15 20
Time Complexity
Average Worst
Operation
Case Case
Insertion O(log n) O(n)
Search O(log n) O(n)
Traversal O(n) O(n)
The worst case occurs when the tree becomes skewed, resembling a linked list.