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:

</>
Copy
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):

</>
Copy
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:

  1. The insert() function checks if the root is None. If it is, a new node is created with the given key.
  2. If the root is not None, the function compares the new key with root.key to decide whether to traverse to the left or right subtree.
  3. The recursive call insert(root.left, key) or insert(root.right, key) is made accordingly until the correct position is found.
  4. 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:

</>
Copy
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):

</>
Copy
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:

  1. The deleteNode() function locates the node to be deleted by comparing the given key with root.key.
  2. If the key is less than or greater than root.key, it recursively searches in the left or right subtree.
  3. Once the node is found, it handles three cases:
    1. If the node has no left child, it returns the right child.
    2. If the node has no right child, it returns the left child.
    3. If the node has two children, it finds the inorder successor using findMin(), replaces the node’s key, and recursively deletes the successor.
  4. 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:

</>
Copy
function preorder(root):
    if root is not NULL:
        visit(root)
        preorder(root.left)
        preorder(root.right)

Python Code (main.py):

</>
Copy
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:

  1. The preorder() function first checks if the current root is not None.
  2. It then prints the value of the node (visiting the root).
  3. The function recursively calls itself to traverse the left subtree.
  4. 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:

</>
Copy
function inorder(root):
    if root is not NULL:
        inorder(root.left)
        visit(root)
        inorder(root.right)

Python Code (main.py):

</>
Copy
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:

  1. The inorder() function recursively traverses the left subtree first.
  2. After the left subtree, it prints the value of the current node (visiting the root).
  3. 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:

</>
Copy
function postorder(root):
    if root is not NULL:
        postorder(root.left)
        postorder(root.right)
        visit(root)

Python Code (main.py):

</>
Copy
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:

  1. The postorder() function first recursively traverses the left subtree.
  2. Then, it traverses the right subtree recursively.
  3. 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:

</>
Copy
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):

</>
Copy
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:

  1. Insert a node: Using recursive logic to add nodes while maintaining binary search tree properties.
  2. Delete a node: Handling the deletion for nodes with zero, one, or two children.
  3. 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.