Binary Tree

An easy-to-understand explanation of the Binary Tree data structure.

What is a Binary Tree?

A Binary Tree is a tree-like data structure in which each node has at most two children: a left child and a right child. The top node of the tree is called the root, and from there, each child can have its own children, creating a hierarchical structure.

In simple terms, a Binary Tree is like a family tree where each person (node) can have up to two children. The tree starts from a single ancestor (the root), and each level of the tree contains the descendants (children) of the previous level.

How a Binary Tree Works

Each node in a Binary Tree contains:

Data: The value or information stored at that node.
Left Child: A reference to the left child node, which itself is the root of a subtree.
Right Child: A reference to the right child node, also a root of a subtree.

I can think of the Binary Tree as a set of decisions: at each node, I can choose to go left or right based on the value I’m searching for, similar to how I might navigate through options when making choices in a decision-making process.

Here’s an example of a simple Binary Tree:

The root is 10.
The left child of 10 is 5, and the right child is 15.
Similarly, 5 has left and right children: 2 and 7, and 15 has 12 and 20.

Types of Binary Trees

There are several types of Binary Trees based on their properties:

Full Binary Tree: Every node has either 0 or 2 children. No node has just one child.
Perfect Binary Tree: All levels are completely filled. Every leaf is at the same level.
Complete Binary Tree: All levels are completely filled except possibly for the last one, and all nodes are as far left as possible.
Binary Search Tree (BST): A Binary Tree where the left child’s value is smaller, and the right child’s value is larger than the parent’s value.

Operations on a Binary Tree

Here are some operations I can perform on a Binary Tree:

Insertion: Add a new node to the tree. O(log n) for balanced trees and O(n) for unbalanced trees
Traversal: Visit all nodes in a specific order (pre-order, in-order, post-order). O(n)
Searching: Find a specific value in the tree. O(n) for leaf nodes and O(1) for root node
Deletion: Remove a node from the tree. O(log n) for balanced trees and O(n) for unbalanced trees
Height Calculation: Determine the number of levels in the tree. O(n)

Applications of Binary Trees

Binary Trees are very useful in various scenarios:

Binary Search Trees (BSTs) are used for efficient searching and sorting of data. Since the values on the left are smaller and on the right are larger, it’s easy to find elements.
Expression Trees: Binary Trees are used to represent mathematical expressions, where the leaves are operands and internal nodes are operators.
Huffman Encoding: Binary Trees are also used in data compression techniques like Huffman encoding, where the tree represents the frequency of characters.
Priority Queues: Binary Trees can be used to implement heaps (min-heaps or max-heaps), which are useful in priority queues.

Code Examples

I’ve included examples in C++, Python, and Java below, where I perform basic operations like inserting nodes and traversing the tree. Let’s walk through how this is done in each language:

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

class BinaryTree:
    def __init__(self):
        self.root = None

    # Insert a node into the binary tree
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    # Helper function to insert a node recursively
    def _insert(self, root, value):
        if value < root.data:
            if root.left is None:
                root.left = Node(value)
            else:
                self._insert(root.left, value)
        else:
            if root.right is None:
                root.right = Node(value)
            else:
                self._insert(root.right, value)

    # In-order traversal of the tree
    def in_order(self):
        self._in_order(self.root)

    def _in_order(self, root):
        if root:
            self._in_order(root.left)
            print(root.data, end=" ")
            self._in_order(root.right)

# Example usage
tree = BinaryTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(2)
tree.insert(7)

print("In-order traversal: ", end="")
tree.in_order()  # Should print 2 5 7 10 15
print()

Problems to Solve

Important Problems on Trees

Resources

Trees

Binary Search Tree