DSA — Trees, Graphs & Binary Trees

Trees are hierarchical — one root, child nodes, no cycles. File systems and HTML DOM are trees.

Trees

Trees are hierarchical — one root, child nodes, no cycles. File systems and HTML DOM are trees.

Traversal: preorder, inorder, postorder visit nodes in different orders.

Real-life example: A company org chart is a tree — CEO at root, teams as branches.

Graphs

Graphs have nodes (vertices) and edges — may be cyclic. Social networks and maps are graphs.

Represent with adjacency list: dict mapping node → neighbors.

Real-life example: A city road map is a graph — intersections are nodes, roads are edges.

Adjacency list

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}
print(graph["A"])

Binary Trees

Each node has at most two children — left and right. Basis for BSTs and heaps.

Binary trees power expression parsers and decision structures.

Real-life example: Binary choices at each step — yes/no questions forming a twenty-questions game tree.

Binary tree node

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

root = TreeNode(10, TreeNode(5), TreeNode(15))
print(root.left.val)

Binary Search Trees

BST: left child < node < right child. Enables O(log n) search when balanced.

Inorder traversal of BST prints sorted values.

Real-life example: BST is a sorted filing cabinet — go left for smaller names, right for larger.

BST search idea

def search(node, target):
    if not node:
        return False
    if target == node.val:
        return True
    if target < node.val:
        return search(node.left, target)
    return search(node.right, target)

AVL Trees

AVL trees self-balance after inserts — height difference of subtrees ≤ 1.

Guarantees O(log n) operations vs skewed BST.

Real-life example: AVL is a self-leveling shelf — when one side gets too heavy, it rebalances automatically.