Binary Tree

Introduction

A Binary Tree is a foundational data structure in computer science where each node has at most two children, referred to as the left child and right child. It is the basis for more complex trees like Binary Search Trees (BSTs), AVL Trees, Heaps, and Expression Trees.

Binary trees are widely used for representing hierarchical data, parsing expressions, building search systems, and organizing memory-efficient structures. Because of their recursive nature and mathematical properties, they are also a favorite topic in algorithm interviews and academic settings.

Structure of a Binary Tree

Each node in a binary tree contains:

A value or key
A reference to a left child (can be null)
A reference to a right child (can be null)

Visual Representation

       10
      /  \
     5    15
    / \     \
   2   7     20

Here:

10 is the root
5 and 15 are children of 10
2, 7, and 20 are leaf nodes (no children)

Properties of a Binary Tree

Let’s assume a binary tree with n nodes and height h (height = number of edges from root to deepest leaf):

Property	Description
Maximum nodes (height h)	`2^(h+1) - 1`
Minimum nodes (height h)	`h + 1` (a skewed tree)
Maximum height (n nodes)	`n - 1`
Minimum height (n nodes)	`log2(n)` (in a complete tree)
Internal nodes + 1	Equals number of leaves in a full binary tree
In-order traversal	Yields sorted order in Binary Search Trees

Types of Binary Trees

1. Full Binary Tree

Every node has 0 or 2 children.

       1
      / \
     2   3

2. Complete Binary Tree

All levels are completely filled except possibly the last, which is filled left to right.

3. Perfect Binary Tree

All levels are fully filled and all leaf nodes are at the same level.

4. Balanced Binary Tree

For every node, the height difference between left and right subtree is at most 1.

5. Degenerate (Skewed) Binary Tree

Each parent has only one child — effectively a linked list.

Binary Tree Traversals

Binary trees are typically traversed using Depth-First Search (DFS) or Breadth-First Search (BFS).

1. Inorder (Left → Root → Right)

2 → 5 → 7 → 10 → 15 → 20

2. Preorder (Root → Left → Right)

10 → 5 → 2 → 7 → 15 → 20

3. Postorder (Left → Right → Root)

2 → 7 → 5 → 20 → 15 → 10

4. Level-order (Breadth-First)

Uses a queue to visit nodes level by level:

10 → 5 → 15 → 2 → 7 → 20

Binary Tree Implementation in Python

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

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

# Example usage
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.right = Node(20)

inorder(root)
# Output: 2 5 7 10 15 20

Common Binary Tree Algorithms

1. Height of a Tree

def height(root):
    if not root:
        return -1
    return 1 + max(height(root.left), height(root.right))

2. Count Nodes

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

3. Check if Tree is Balanced

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        lh = check(node.left)
        rh = check(node.right)
        if abs(lh - rh) > 1:
            raise Exception("Unbalanced")
        return 1 + max(lh, rh)

    try:
        check(root)
        return True
    except:
        return False

Applications of Binary Trees

Expression Trees (for arithmetic parsing)
Search Trees (Binary Search Tree, AVL Tree)
Heap Trees (used in priority queues)
Syntax Trees (used in compilers)
Decision Trees (machine learning)
File system representations (hierarchical data)
Network routing tables

When to Use a Binary Tree

Binary trees are ideal when:

You want fast insertion, deletion, and search
You need hierarchical representation of data
You require ordered traversal
You plan to upgrade to balanced variants (AVL, Red-Black Trees)

Binary Tree vs Binary Search Tree

Feature	Binary Tree	Binary Search Tree (BST)
Key Constraint	No ordering constraints	Left < Root < Right
Use Case	Generic tree structures	Efficient search and range query
Search Time	O(n)	O(log n) (if balanced)
Insert/Remove	No rules	Must preserve order

Drawbacks of Binary Trees

Without balancing, they can degrade into linear structures
Lookup can become inefficient in unbalanced forms
Poor cache performance compared to flat arrays (e.g., heaps)
No guarantee of optimal height unless structured (e.g., complete trees)

Real-World Analogy

Imagine a family tree: Each person (node) can have up to two children — left and right. The structure allows you to track ancestry, siblings, descendants — all in a hierarchical and navigable way. Binary trees behave similarly.

Binary Tree Interview Questions

Implement inorder, preorder, postorder traversal
Find the lowest common ancestor (LCA) of two nodes
Determine if a binary tree is symmetric
Convert binary tree to doubly linked list
Serialize and deserialize a binary tree
Check if two binary trees are identical

Summary

A Binary Tree is a hierarchical, non-linear data structure that forms the building block for numerous advanced structures in computing. From parsing expressions to managing hierarchical relationships and optimizing searches, binary trees appear in countless systems and algorithms.

Understanding their properties, variations, and traversal methods is essential for every programmer and computer science student.