Binary Tree

---

A Binary Tree is one of the most important and widely used data structures in computer science. It consists of nodes, each with a maximum of two children, referred to as the left child and the right child. Binary trees are used in various applications such as expression evaluation, searching, and sorting.

In this blog post, we will explore the structure of binary trees, the different types of binary trees, and common operations that can be performed on them. Additionally, we will include some Python code examples to help solidify your understanding.

---

What is a Binary Tree?

A Binary Tree is a hierarchical data structure consisting of nodes, where each node has at most two child nodes—commonly referred to as the left and right children. The structure of a binary tree is often depicted visually as a tree with a root node and a branching pattern of nodes connected by edges.

Key Terminology of Binary Tree

• Node: A single element in the tree, consisting of a value or data.
• Root: The top node of the tree, which has no parent.
• Parent: A node that has one or more children.
• Child: A node that is a descendant of another node.
• Leaf: A node that has no children.
• Subtree: A portion of the binary tree, rooted at any node.
• Depth: The number of edges from the root to the node.
• Height: The length of the longest path from the node to a leaf.
• Level: The level of a node is the number of edges from the root to the node.

---

Properties of Binary Trees

1. Acyclic: Binary trees have no cycles, meaning there's no way to start from one node and return to it by traversing other nodes.
2. Unique Path: There is exactly one path between any two nodes in a binary tree.
3. Depth of Binary Tree: The depth is the maximum distance from the root to any leaf node.

Height of a Binary Tree

The height of a binary tree is defined as the number of edges on the longest path from the root to any leaf. For an empty tree, the height is -1, and for a tree with just one node, the height is 0.

---

Types of Binary Trees

There are several types of binary trees, each with unique properties suited for different applications.

1. Full Binary Tree

A full binary tree is a binary tree in which every node has either 0 or 2 children. This means that no node can have just one child.

2. Complete Binary Tree

A complete binary tree is a binary tree where all the levels, except possibly the last, are fully filled, and all the nodes are as far left as possible. This type of tree is used in heap-based data structures like heaps and priority queues.

3. Perfect Binary Tree

A perfect binary tree is one in which all the internal nodes have exactly two children, and all the leaf nodes are at the same level.

4. Balanced Binary Tree

A balanced binary tree is one in which the height of the two subtrees of every node differ by at most one. The AVL tree is an example of a balanced binary tree.

5. Degenerate (or pathological) Binary Tree

A degenerate binary tree is a tree where every parent node has only one child. This effectively makes the tree behave like a linked list.

---

Binary Tree Operations

Several basic operations can be performed on binary trees, including insertion, deletion, searching, and traversal.

1. Insertion in Binary Tree

Insertion in a binary tree typically involves placing a new node at the first available position (in level order), ensuring the tree remains complete or balanced.

Code Example: Insertion in Binary Tree (Level Order)

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

def insert(root, key):
    new_node = Node(key)
    if root is None:
        root = new_node
        return root
    
    queue = []
    queue.append(root)
    
    while queue:
        temp = queue.pop(0)
        
        if not temp.left:
            temp.left = new_node
            return root
        else:
            queue.append(temp.left)
        
        if not temp.right:
            temp.right = new_node
            return root
        else:
            queue.append(temp.right)

# Example of Binary Tree Insertion
root = Node(1)
root = insert(root, 2)
root = insert(root, 3)
root = insert(root, 4)
root = insert(root, 5)

2. Deletion in Binary Tree

Deletion in a binary tree is a bit more involved than insertion, as it requires finding the node to delete and then re-arranging the tree to maintain its structure. In the case of binary search trees (BST), deletion also involves ensuring that the binary search tree property is maintained.

3. Searching in Binary Tree

Searching in a binary tree involves traversing through the nodes of the tree, starting from the root and visiting each node in a specific order (depending on the type of traversal).

4. Tree Traversal

Traversal refers to visiting all the nodes in a specific order. The primary types of tree traversal are:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Level Order Traversal

We will discuss Binary Tree Traversal methods in another dedicated post, but here’s a brief overview of traversal orders:

• Preorder: Visit root, left subtree, right subtree.
• Inorder: Visit left subtree, root, right subtree.
• Postorder: Visit left subtree, right subtree, root.
• Level Order: Visit nodes level by level.

---

Code Example: Binary Tree Traversal

Here’s how to implement inorder traversal for a binary tree in Python:

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)  # Visit left subtree
        print(root.value, end=" ")  # Visit root
        inorder_traversal(root.right)  # Visit right subtree

# Perform Inorder Traversal
print("Inorder Traversal:")
inorder_traversal(root)

Output:

Inorder Traversal:
4 2 5 1 3

---

Applications of Binary Trees

1. Expression Evaluation: Binary trees are often used to represent mathematical expressions. The operations in an expression can be represented as internal nodes, with operands as leaves.
2. Database Indexing: In data structures like Binary Search Trees (BST), binary trees provide an efficient way to store and retrieve data.
3. Heap Data Structures: Binary trees form the basis for heap structures used in implementing priority queues.
4. Searching and Sorting: Binary search trees (BSTs) allow for efficient searching, insertion, and deletion operations with an average time complexity of O(log n).

---

---