Unit 4: Trees

Python Implementation

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


def inorder(root):
    """Left → Root → Right. Gives sorted order for BST."""
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)

def preorder(root):
    """Root → Left → Right. Used to serialize/copy a tree."""
    if root:
        print(root.val, end=" ")
        preorder(root.left)
        preorder(root.right)

def postorder(root):
    """Left → Right → Root. Used to delete a tree safely."""
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val, end=" ")


# Build tree:     1
#                / \
#               2   3
#              / \
#             4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("In-order:  ", end=""); inorder(root); print()
print("Pre-order: ", end=""); preorder(root); print()
print("Post-order:", end=""); postorder(root); print()

C Implementation

C
#include <stdio.h>
#include <stdlib.h>

struct Node { int data; struct Node *left, *right; };

struct Node* newNode(int val) {
    struct Node* n = (struct Node*)malloc(sizeof(struct Node));
    n->data = val; n->left = n->right = NULL; return n;
}

void inorder(struct Node* r) { if(r){inorder(r->left);printf("%d ",r->data);inorder(r->right);} }
void preorder(struct Node* r) { if(r){printf("%d ",r->data);preorder(r->left);preorder(r->right);} }
void postorder(struct Node* r) { if(r){postorder(r->left);postorder(r->right);printf("%d ",r->data);} }

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2); root->right = newNode(3);
    root->left->left = newNode(4); root->left->right = newNode(5);
    printf("In:  "); inorder(root); printf("\n");
    printf("Pre: "); preorder(root); printf("\n");
    printf("Post:"); postorder(root); printf("\n");
    return 0;
}

Python
def root_to_leaf_paths(root, path, all_paths):
    """Find every path from root to a leaf node.
    Uses backtracking — add current node, recurse, then remove."""
    if not root:
        return
    
    path.append(root.val)                  # Add current node to path
    
    if not root.left and not root.right:   # Leaf — record complete path
        all_paths.append(list(path))
    else:
        root_to_leaf_paths(root.left, path, all_paths)
        root_to_leaf_paths(root.right, path, all_paths)
    
    path.pop()                             # Backtrack — remove current node


# Tree:     1
#          / \
#         2   3
#        / \
#       4   5
paths = []
root_to_leaf_paths(root, [], paths)
for p in paths:
    print(" → ".join(map(str, p)))

C
void printPaths(struct Node* root, int path[], int pathLen) {
    if(!root) return;
    path[pathLen++] = root->data;
    if(!root->left && !root->right) {
        for(int i=0;i<pathLen;i++) printf("%d%s",path[i],i<pathLen-1?" -> ":"");
        printf("\n");
    }
    printPaths(root->left, path, pathLen);
    printPaths(root->right, path, pathLen);
}

Python
def find_lca(root, p, q):
    """Find the Lowest Common Ancestor of nodes p and q.
    
    LCA is the deepest node that is an ancestor of both p and q.
    Industry: Nykaa finds the common category between two products.
              Git uses LCA to find the merge-base of two branches.
    
    Algorithm: If both p and q are in the left subtree, LCA is in left.
    If both in right, LCA is in right. If they split, current node IS the LCA.
    """
    if not root or root.val == p or root.val == q:
        return root                       # Base: found p, q, or null
    
    left = find_lca(root.left, p, q)      # Search left subtree
    right = find_lca(root.right, p, q)    # Search right subtree
    
    if left and right:                    # p and q are on different sides
        return root                       # Current node IS the LCA!
    
    return left if left else right       # Both on same side — pass up


# Tree:     1
#          / \
#         2   3
#        / \
#       4   5
result = find_lca(root, 4, 5)
print(f"LCA(4, 5) = {result.val}")      # 2
result = find_lca(root, 4, 3)
print(f"LCA(4, 3) = {result.val}")      # 1

C
struct Node* lca(struct Node* root, int p, int q) {
    if(!root || root->data==p || root->data==q) return root;
    struct Node* l = lca(root->left, p, q);
    struct Node* r = lca(root->right, p, q);
    if(l && r) return root;
    return l ? l : r;
}

Python
class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        """Insert value maintaining BST property. O(log n) avg."""
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)           # Base: empty spot found
        if val < node.val:
            node.left = self._insert(node.left, val)   # Go left
        elif val > node.val:
            node.right = self._insert(node.right, val)  # Go right
        # If val == node.val, skip (no duplicates)
        return node

    def delete(self, val):
        """Delete value from BST. Three cases:
        1. Leaf: just remove
        2. One child: replace with child
        3. Two children: replace with in-order successor (min of right subtree)"""
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if not node:
            return node
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:                              # Found the node to delete
            if not node.left:              # Case 1 & 2: no left child
                return node.right
            if not node.right:             # Case 2: no right child
                return node.left
            # Case 3: two children — find in-order successor
            successor = self._find_min(node.right)
            node.val = successor.val         # Copy successor's value
            node.right = self._delete(node.right, successor.val)  # Delete successor
        return node

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)


# === Driver ===
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(v)

print("In-order:", bst.inorder())
print("Search 40:", "Found" if bst.search(40) else "Not found")
bst.delete(50)
print("After deleting 50:", bst.inorder())

C Implementation

C
struct Node* bstInsert(struct Node* root, int val) {
    if(!root) return newNode(val);
    if(val < root->data) root->left = bstInsert(root->left, val);
    else if(val > root->data) root->right = bstInsert(root->right, val);
    return root;
}

struct Node* findMin(struct Node* n) { while(n->left) n=n->left; return n; }

struct Node* bstDelete(struct Node* root, int val) {
    if(!root) return root;
    if(val < root->data) root->left = bstDelete(root->left, val);
    else if(val > root->data) root->right = bstDelete(root->right, val);
    else {
        if(!root->left) { struct Node* t=root->right; free(root); return t; }
        if(!root->right) { struct Node* t=root->left; free(root); return t; }
        struct Node* s = findMin(root->right);
        root->data = s->data;
        root->right = bstDelete(root->right, s->data);
    }
    return root;
}

Python
def kth_smallest(root, k):
    """In-order traversal gives sorted order. The k-th element visited
    is the k-th smallest. O(h + k) time, O(h) space.
    
    Industry: "Show the 5th cheapest product" on Nykaa/Flipkart."""
    stack = []
    current = root
    count = 0
    
    while stack or current:
        while current:                    # Go to leftmost node
            stack.append(current)
            current = current.left
        
        current = stack.pop()             # Visit node
        count += 1
        if count == k:
            return current.val            # Found k-th smallest!
        
        current = current.right           # Move to right subtree
    
    return None                          # k > number of nodes


def kth_largest(root, k):
    """Reverse in-order (Right, Root, Left) gives descending order.
    The k-th element visited is the k-th largest."""
    stack = []
    current = root
    count = 0
    
    while stack or current:
        while current:                    # Go to rightmost node
            stack.append(current)
            current = current.right
        
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        
        current = current.left
    
    return None


# BST: [20, 30, 40, 50, 60, 70, 80]
print(f"3rd smallest: {kth_smallest(bst.root, 3)}")
print(f"2nd largest:  {kth_largest(bst.root, 2)}")