Module 9 : Trees

A tree is a non-linear hierarchical data structure used to represent relationships.
Unlike arrays or linked lists, trees allow multiple paths, branching, and hierarchy, making them ideal for modeling real-world systems.

Examples:

• File systems
• Organization charts
• DOM structure
• Databases & indexes

Binary Trees

A binary tree is a tree in which:

• Each node has at most two children
• Children are called left and right

Node structure:

class TreeNode {
    int val;
    TreeNode left, right;
}

Tree Terminology

Understanding terminology avoids confusion later.

• Root: Topmost node
• Parent: Node with children
• Child: Node derived from parent
• Leaf: Node with no children
• Siblings: Nodes with same parent
• Subtree: Tree formed from any node
• Edge: Connection between nodes
• Level: Distance from root (root = level 0)

Tree Traversal (DFS & BFS)

Traversal means visiting every node exactly once.

DFS (Depth First Search)

Explores deep before wide.

Types of DFS Traversal

Inorder (Left → Root → Right)

Used in BST to get sorted order.

void inorder(TreeNode root){
    if(root == null) return;
    inorder(root.left);
    System.out.print(root.val);
    inorder(root.right);
}

---

Preorder (Root → Left → Right)

Used in tree construction & serialization.

void preorder(TreeNode root){
    if(root == null) return;
    System.out.print(root.val);
    preorder(root.left);
    preorder(root.right);
}

---

Postorder (Left → Right → Root)

Used in deletion and bottom-up problems.

void postorder(TreeNode root){
    if(root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val);
}

BFS (Breadth First Search)

Traverses level by level using a queue.

void levelOrder(TreeNode root){
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while(!q.isEmpty()){
        TreeNode curr = q.poll();
        System.out.print(curr.val);
        if(curr.left != null) q.add(curr.left);
        if(curr.right != null) q.add(curr.right);
    }
}

Recursive vs Iterative Traversal

Recursive

• Cleaner code
• Uses call stack
• Risk of stack overflow

Iterative

• Uses explicit stack or queue
• More control
• Preferred in memory-critical systems

Height & Depth

• Height of node: Longest path from node to leaf
• Height of tree: Height of root
• Depth of node: Distance from root

int height(TreeNode root){
    if(root == null) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

Diameter of Tree

Definition

The longest path between any two nodes.

May or may not pass through root.

Optimized Approach

Calculate height and update diameter simultaneously.

int diameter = 0;

int height(TreeNode root){
    if(root == null) return 0;
    int lh = height(root.left);
    int rh = height(root.right);
    diameter = Math.max(diameter, lh + rh);
    return 1 + Math.max(lh, rh);
}

Balanced Binary Tree

A tree is balanced if:

|height(left) − height(right)| ≤ 1

for every node.

boolean isBalanced(TreeNode root){
    return check(root) != -1;
}

int check(TreeNode root){
    if(root == null) return 0;
    int lh = check(root.left);
    if(lh == -1) return -1;
    int rh = check(root.right);
    if(rh == -1) return -1;
    if(Math.abs(lh - rh) > 1) return -1;
    return 1 + Math.max(lh, rh);
}

Lowest Common Ancestor (LCA)

Definition

The deepest node that is ancestor of both nodes.

Binary Tree Approach

TreeNode lca(TreeNode root, int p, int q){
    if(root == null || root.val == p || root.val == q)
        return root;

    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);

    if(left != null && right != null)
        return root;

    return left != null ? left : right;
}

Path Sum Problems

Example

Check if a root-to-leaf path equals target sum.

boolean hasPathSum(TreeNode root, int sum){
    if(root == null) return false;
    if(root.left == null && root.right == null)
        return sum == root.val;

    return hasPathSum(root.left, sum - root.val) ||
           hasPathSum(root.right, sum - root.val);
}

Variants include:

• Count paths
• Any path (not necessarily root)

Serialization & Deserialization

Why Needed?

To store or transmit trees.

Serialization (Preorder)

void serialize(TreeNode root, StringBuilder sb){
    if(root == null){
        sb.append("null,");
        return;
    }
    sb.append(root.val).append(",");
    serialize(root.left, sb);
    serialize(root.right, sb);
}

Deserialization

TreeNode deserialize(Queue<String> q){
    String val = q.poll();
    if(val.equals("null")) return null;

    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserialize(q);
    node.right = deserialize(q);
    return node;
}

Binary Search Trees (BST)

A BST is a binary tree where:

Left < Root < Right

This property enables logarithmic search.

BST Operations

Search

TreeNode search(TreeNode root, int key){
    if(root == null || root.val == key)
        return root;
    if(key < root.val)
        return search(root.left, key);
    return search(root.right, key);
}

Insert

TreeNode insert(TreeNode root, int val){
    if(root == null) return new TreeNode(val);
    if(val < root.val)
        root.left = insert(root.left, val);
    else
        root.right = insert(root.right, val);
    return root;
}

Delete (Concept)

• No child → remove
• One child → replace
• Two children → replace with inorder successor

Validate BST

boolean isValid(TreeNode root){
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode root, long min, long max){
    if(root == null) return true;
    if(root.val <= min || root.val >= max)
        return false;
    return validate(root.left, min, root.val) &&
           validate(root.right, root.val, max);
}

Kth Smallest Element

Inorder traversal gives sorted order.

int count = 0;
int ans;

void inorder(TreeNode root, int k){
    if(root == null) return;
    inorder(root.left, k);
    count++;
    if(count == k) ans = root.val;
    inorder(root.right, k);
}

Floor & Ceil in BST

• Floor: Greatest value ≤ key
• Ceil: Smallest value ≥ key

int floor(TreeNode root, int key){
    int res = -1;
    while(root != null){
        if(root.val == key) return root.val;
        if(root.val < key){
            res = root.val;
            root = root.right;
        } else {
            root = root.left;
        }
    }
    return res;
}

Convert Sorted Array to BST

Creates a height-balanced BST.

TreeNode build(int[] arr, int l, int r){
    if(l > r) return null;
    int mid = (l + r) / 2;
    TreeNode root = new TreeNode(arr[mid]);
    root.left = build(arr, l, mid - 1);
    root.right = build(arr, mid + 1, r);
    return root;
}