Chapter 12 – Binary Trees and Binary Search Trees (BST)

Chapter 12: Binary Trees and Binary Search Trees (BST)

---

Welcome to the fascinating world of Trees! Trees are one of the most fundamental data structures in computer science, and they are widely used in various applications like file systems, databases, and more. This chapter focuses on two essential types of trees: Binary Trees and Binary Search Trees (BSTs).

---

What is a Tree?

A Tree is a non-linear data structure composed of nodes. It is a hierarchical structure with a root node and sub-nodes, each connected by edges. Unlike arrays, linked lists, stacks, or queues, trees are nonlinear and allow for more complex relationships between elements.

A tree follows these rules:

• Each node contains a value or data.
• The root node is the topmost node in the tree.
• Each node has zero or more child nodes.
• Each node can only have one parent (except for the root, which has no parent).

---

What is a Binary Tree?

A Binary Tree is a type of tree where each node can have at most two children, often referred to as the left child and right child.

Characteristics of a Binary Tree:

1. Node: Contains data, and two pointers (left and right).
2. Edge: The connection between two nodes.
3. Root: The topmost node in the tree.
4. Leaf Node: A node with no children.
5. Height: The number of edges from the root to the deepest leaf.

Structure of a Binary Tree

Here’s a simple binary tree:

       10
      /  \
     5    15
    / \   / \
   3   7 12  20

In this example:

• 10 is the root.
• 5 and 15 are children of 10.
• 3, 7, 12, and 20 are leaf nodes.

---

Types of Binary Trees

1. Full Binary Tree: Every node has either 0 or 2 children.
2. Complete Binary Tree: All levels are completely filled, except possibly the last level, which is filled from left to right.
3. Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same level.
4. Balanced Binary Tree: The height of the tree is balanced, meaning the difference between the height of the left and right subtrees for any node is at most 1.

---

What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a special kind of binary tree where the nodes are arranged in a specific order. In a BST:

• The left subtree of a node contains only nodes with values less than the node’s value.
• The right subtree contains only nodes with values greater than the node’s value.
• Both the left and right subtrees must also be binary search trees.

This property makes BSTs highly efficient for searching, insertion, and deletion operations.

---

Example of a Binary Search Tree

Consider the following tree:

       15
      /  \
     10   25
    / \   / \
   5  12 20 30

In this BST:

• Nodes to the left of 15 are smaller than 15 (i.e., 10, 5, 12).
• Nodes to the right of 15 are greater than 15 (i.e., 25, 20, 30).
• This ordering ensures efficient search operations.

---

Operations on Binary Search Trees

1. Insertion

To insert a new element into a BST, we start at the root and compare the new element with the current node:

• If it is smaller, we move to the left subtree.
• If it is greater, we move to the right subtree.
• We continue this until we find an empty spot, where we insert the new node.

Example:
Inserting 8 into the following BST:

       10
      /  \
     5   15
    / \
   3   7

• Since 8 is greater than 5 and less than 10, we move to the right child of 5 and place it there:

       10
      /  \
     5   15
    / \
   3   7
        \
         8

2. Deletion

To delete a node from a BST, we must consider three cases:

• Case 1: The node to be deleted is a leaf (has no children).
• Case 2: The node to be deleted has one child.
• Case 3: The node to be deleted has two children.

Example:
Let’s delete the node 7 from the tree above. Since it has one child (8), we simply replace 7 with 8.

       10
      /  \
     5   15
    / \
   3   8

3. Search

To search for a value in a BST:

• Start at the root.
• If the value is smaller than the current node, move left; if it’s greater, move right.
• Repeat this process until you find the value or reach a NULL node (the value does not exist in the tree).

---

Applications of Binary Search Trees

1. Search Operations: Due to the structured order, searching for an element in a BST is more efficient than in unsorted arrays or linked lists.
2. In-memory databases: BSTs are commonly used in database indexing where efficient searching is crucial.
3. Network Routing: BSTs help in storing hierarchical data, which can be efficiently searched, like network routes.
4. Dynamic Data Structures: In scenarios like building self-balancing trees in applications, BSTs form the backbone.

Systems like Emancipation Edutech Private Limited often use Binary Search Trees to manage student records efficiently by indexing them according to registration numbers.

For free educational resources, visit digilearn.cloud, where you can access this book and much more!

---

Binary Tree Traversal Methods

To interact with the data in a binary tree, we need to traverse it. There are three primary traversal techniques:

1. In-order Traversal (Left, Root, Right)

This traversal visits nodes in ascending order in a BST.

Visit Left Subtree -> Visit Root -> Visit Right Subtree

Example:

For the tree:

       10
      /  \
     5   15
    / \
   3   7

The in-order traversal would be: 3 -> 5 -> 7 -> 10 -> 15.

2. Pre-order Traversal (Root, Left, Right)

This traversal visits the root node first, followed by the left subtree, and then the right subtree.

Visit Root -> Visit Left Subtree -> Visit Right Subtree

Example:

For the same tree:

       10
      /  \
     5   15
    / \
   3   7

The pre-order traversal would be: 10 -> 5 -> 3 -> 7 -> 15.

3. Post-order Traversal (Left, Right, Root)

This traversal visits the left subtree, then the right subtree, and finally the root node.

Visit Left Subtree -> Visit Right Subtree -> Visit Root

Example:

For the tree:

       10
      /  \
     5   15
    / \
   3   7

The post-order traversal would be: 3 -> 7 -> 5 -> 15 -> 10.

---

Advantages of Binary Search Trees

1. Efficient Searching: The time complexity of searching in a BST is O(log n), making it faster than unsorted structures.
2. Dynamic Data Structure: Nodes can be inserted or deleted dynamically without reorganizing the entire structure, unlike arrays.
3. Ordered Structure: The BST ensures that data remains sorted, which is useful in many real-world applications.

---

Disadvantages of Binary Search Trees

1. Unbalanced BSTs: In the worst case (if the tree is not balanced), the time complexity of search, insert, and delete operations becomes O(n).
2. Space Complexity: BSTs can sometimes take up more memory due to the need to store pointers in each node.

---

Conclusion

Binary Trees and Binary Search Trees (BSTs) are foundational structures in computer science, offering an efficient way to store, search, and manage hierarchical data. Understanding their structure, operations, and applications will enable you to solve many real-world problems with ease.

In the next chapter, we will dive into AVL Trees and Red-Black Trees, which are self-balancing trees that optimize performance when working with large datasets.

Keep learning, and don’t forget to visit digilearn.cloud for more resources!

---