Binary Tree — Explained with Examples

A binary tree is a hierarchical data structure where each node has at most two children, enabling efficient searching, sorting, and traversal.

Binary trees consist of nodes with a value, a left child, and a right child. Types include full (every node has 0 or 2 children), perfect (all interior nodes have 2 children and leaves are at the same level), complete (all levels filled except possibly the last, filled left to right), and balanced (height difference between subtrees is bounded). Traversals include preorder, inorder, and postorder.

Think of a binary tree like a company org chart. Each manager (node) oversees at most two direct reports (children). The CEO is the root. The hierarchy allows you to find any employee quickly by moving left or right through the chain of command.

Binary trees underpin many important data structures: binary search trees, heaps, and expression trees. The height of a balanced binary tree with n nodes is O(log n), making operations efficient.

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

# Binary tree traversals
def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")

# Build a simple tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

inorder(root)   # 4 2 5 1 3

Binary trees come in many variants: AVL trees (self-balancing), red-black trees, segment trees, and Fenwick trees, each optimized for specific operations.

Binary Search Tree, BFS, DFS, Heap, Trie

BST Properties