Basic Operations on Binary Trees
This tutorial explains the basic operations on binary trees including insertion, deletion, and various traversal techniques. We provide both pseudo code for general understanding and Python code for language-specific examples.
1 Insertion of a Node
In this example, we will insert a new node into a binary search tree. The pseudo code outlines the logic and the Python code demonstrates how to implement it. The insertion process checks if the tree is empty, and if not, compares the new value with the current node to decide whether to traverse left or right.
Pseudo Code:
function insert(root, value):
if root is NULL:
root = new Node(value)
else if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
Python Code (main.py):
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
# Example usage
if __name__ == "__main__":
root = None
# Inserting nodes into the binary search tree
for key in [50, 30, 20, 40, 70, 60, 80]:
root = insert(root, key)
Explanation:
- The
insert()
function checks if theroot
isNone
. If it is, a new node is created with the given key. - If the
root
is notNone
, the function compares the new key withroot.key
to decide whether to traverse to the left or right subtree. - The recursive call
insert(root.left, key)
orinsert(root.right, key)
is made accordingly until the correct position is found. - Once inserted, the updated tree is returned.
2 Deletion of a Node
In this example, we will delete a node from a binary search tree. The deletion operation handles three cases: deleting a leaf node, a node with one child, and a node with two children. When a node with two children is deleted, we find its inorder successor to replace it.
Pseudo Code:
function deleteNode(root, key):
if root is NULL:
return root
if key < root.value:
root.left = deleteNode(root.left, key)
else if key > root.value:
root.right = deleteNode(root.right, key)
else:
if root.left is NULL:
temp = root.right
delete root
return temp
else if root.right is NULL:
temp = root.left
delete root
return temp
temp = findMin(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
Python Code (main.py):
def findMin(node):
while node.left:
node = node.left
return node
def deleteNode(root, key):
if root is None:
return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif key > root.key:
root.right = deleteNode(root.right, key)
else:
# Node with one child or no child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Node with two children: Get the inorder successor
temp = findMin(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
# Example usage
if __name__ == "__main__":
# Construct the binary search tree
keys = [50, 30, 20, 40, 70, 60, 80]
root = None
for key in keys:
root = insert(root, key)
# Delete a node with key 20 (a leaf node)
root = deleteNode(root, 20)
Explanation:
- The
deleteNode()
function locates the node to be deleted by comparing the givenkey
withroot.key
. - If the key is less than or greater than
root.key
, it recursively searches in the left or right subtree. - Once the node is found, it handles three cases:
- If the node has no left child, it returns the right child.
- If the node has no right child, it returns the left child.
- If the node has two children, it finds the inorder successor using
findMin()
, replaces the node’s key, and recursively deletes the successor.
- The
findMin()
function traverses the left children to find the minimum key in the right subtree.
3 Traversal Techniques
Traversal of a binary tree means visiting all the nodes in a particular order. In this section, we cover four main traversal techniques with both pseudo code and Python examples.
1 Preorder Traversal (Root → Left → Right)
In Preorder Traversal, the process is to visit the root first, then traverse the left subtree, and finally traverse the right subtree.
Pseudo Code:
function preorder(root):
if root is not NULL:
visit(root)
preorder(root.left)
preorder(root.right)
Python Code (main.py):
def preorder(root):
if root:
print(root.key, end=" ")
preorder(root.left)
preorder(root.right)
# Example usage for preorder traversal
if __name__ == "__main__":
print("Preorder Traversal:")
preorder(root)
print() # For a new line
Explanation:
- The
preorder()
function first checks if the currentroot
is notNone
. - It then prints the value of the node (visiting the root).
- The function recursively calls itself to traverse the left subtree.
- After the left subtree, it recursively traverses the right subtree.
2 Inorder Traversal (Left → Root → Right)
In Inorder Traversal, the left subtree is visited first, then the root, and finally the right subtree.
Pseudo Code:
function inorder(root):
if root is not NULL:
inorder(root.left)
visit(root)
inorder(root.right)
Python Code (main.py):
def inorder(root):
if root:
inorder(root.left)
print(root.key, end=" ")
inorder(root.right)
# Example usage for inorder traversal
if __name__ == "__main__":
print("Inorder Traversal:")
inorder(root)
print()
Explanation:
- The
inorder()
function recursively traverses the left subtree first. - After the left subtree, it prints the value of the current node (visiting the root).
- Finally, it recursively traverses the right subtree.
3 Postorder Traversal (Left → Right → Root)
In Postorder Traversal, the left subtree is visited first, then the right subtree, and finally the root node.
Pseudo Code:
function postorder(root):
if root is not NULL:
postorder(root.left)
postorder(root.right)
visit(root)
Python Code (main.py):
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.key, end=" ")
# Example usage for postorder traversal
if __name__ == "__main__":
print("Postorder Traversal:")
postorder(root)
print()
Explanation:
- The
postorder()
function first recursively traverses the left subtree. - Then, it traverses the right subtree recursively.
- Finally, it prints the current node’s value (visiting the root last).
3 Level Order Traversal (Breadth-First Search)
Level Order Traversal visits nodes level by level from top to bottom, using a queue to keep track of the nodes to be processed.
Pseudo Code:
function levelOrder(root):
if root is NULL:
return
queue = new Queue()
enqueue(root)
while queue is not empty:
node = dequeue()
visit(node)
if node.left is not NULL:
enqueue(node.left)
if node.right is not NULL:
enqueue(node.right)
Python Code (main.py):
from collections import deque
def levelOrder(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.key, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Example usage for level order traversal
if __name__ == "__main__":
print("Level Order Traversal:")
levelOrder(root)
print()
Conclusion
In this tutorial, we covered the basic operations on binary trees. We demonstrated how to:
- Insert a node: Using recursive logic to add nodes while maintaining binary search tree properties.
- Delete a node: Handling the deletion for nodes with zero, one, or two children.
- Traverse the tree: Implementing Preorder, Inorder, Postorder, and Level Order traversals to visit nodes in different orders.
By understanding these operations, you can efficiently manage binary trees and build more complex data structures and algorithms.