Traversal in a Binary Tree means visiting each node in a specific order. There are three main types of traversal:
✅ 1. Inorder Traversal (Left ➝ Root ➝ Right)
-
Used for: Getting nodes in ascending order in BST.
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=' ')
inorder(root.right)
✅ 2. Preorder Traversal (Root ➝ Left ➝ Right)
-
Used for: Copying the tree or creating prefix expressions.
def preorder(root):
if root:
print(root.data, end=' ')
preorder(root.left)
preorder(root.right)
✅ 3. Postorder Traversal (Left ➝ Right ➝ Root)
-
Used for: Deleting the tree or evaluating postfix expressions.
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.data, end=' ')
✅ 4. Level Order Traversal (Breadth-First)
-
Used for: Traversing level by level (BFS).
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.data, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
🔰 Binary Tree Node Class Example
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
🔁 Example Usage
# Create tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# Call traversal functions
print("Inorder:")
inorder(root)
print("\nPreorder:")
preorder(root)
print("\nPostorder:")
postorder(root)
print("\nLevel Order:")
level_order(root)
No comments:
Post a Comment