DSA — Binary Trees

What is a Binary Tree?

A tree where each node has at most two children.

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

Traversals

# Preorder: Root → Left → Right
def preorder(root):
    if root:
        print(root.data)
        preorder(root.left)
        preorder(root.right)

# Inorder: Left → Root → Right
def inorder(root):
    if root:
        inorder(root.left)
        print(root.data)
        inorder(root.right)

# Postorder: Left → Right → Root
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data)

Height and Size

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

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

Count Leaves

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

Mini Practice

1. Implement a binary tree
2. Perform all traversals
3. Calculate height and size
4. Count leaf nodes

Up Next

Continue with Binary Search Trees — BST operations.