Understanding Searching, Insertion, and Deletion in Binary Trees

Binary trees, with their branching structure, are like well-organized libraries. But how do we efficiently find the book we need (searching), add a new book (insertion), or remove an outdated one (deletion)? This blog post delves into these fundamental operations in binary trees, equipping you with the knowledge to navigate and manipulate data effectively.

1. Searching:

Imagine searching for a specific book in a library. You wouldn't start at the last shelf and work your way back – you'd likely use some order (alphabetical, Dewey Decimal). Binary search trees (BSTs) leverage a similar principle for efficient searching:

• We start at the root node.

• If the data we're searching for is less than the root's data, we move to the left subtree.

• If the data is greater, we move to the right subtree.

• We repeat this comparison process until we either find the data or reach a leaf node (indicating the data doesn't exist in the tree).

Diagram:

      50
     /  \
    30   70
   / \   / \
  20  40 60  80
         \
          90

Here, to search for 60:

1. Start at the root (50).

2. 60 is greater than 50, so move right.

3. We reach 60, our target node (search successful).

2. Insertion:

Adding a new book to a library requires finding the appropriate shelf based on its title. Similarly, insertion in a binary tree involves finding the correct position to maintain the BST property:

• We traverse the tree like searching, comparing the new data with existing nodes.

• If an empty position is found (a leaf node), we create a new node with the new data and link it as the child of the appropriate parent node.

• The key is to insert the new node such that the BST property (left subtree elements are less than the root, right subtree elements are greater) is preserved.

Diagram:

      50
     /  \
    30   70
   / \   / \
  20  40 60  80
         \
          90

(Inserting 15)

      50
     /  \
    30   70
   / \   / \
  20  40 60  80
 /        \
15         90

Here, to insert 15:

1. Traverse left from the root (50) as 15 is less.

2. We reach an empty position (leaf node) below 20.

3. Create a new node with 15 and link it as the left child of 20.

3. Deletion:

Removing a book from a library might involve shifting other books to maintain order. Deleting a node from a binary tree follows a similar approach:

• We first find the node to be deleted.

• There are three cases to consider:

• Node with no child nodes (leaf node): Simply remove the node.

• Node with one child node: Promote the child node to take the place of the deleted node.

• Node with two child nodes: This is the most complex case. We find the inorder successor (the smallest element in the right subtree of the node to be deleted). We swap the data of the node to be deleted with the inorder successor, and then delete the inorder successor (which will have at most one child node).

Diagram:

      50
     /  \
    30   70 (Node to delete)
   / \   / \
  20  40 60  80
         \
          90

(Deleting 70)

      50
     /  \
    30   80 (Inorder successor replaces 70)
   / \   / \
  20  40 60  90
         \
          NULL  (90 replaces 70 and then deleted)

Here, to delete 70:

1. Find 70 (the node to delete).

2. 70 has two child nodes.

3. Find the inorder successor (80).

4. Swap the data of 70 and 80.

5. Delete 80 (which has only one child node).

Conclusion:

By mastering searching, insertion, and deletion operations in binary trees, you unlock the ability to efficiently navigate, manipulate