Binary Tree Traversals

from typing import List, Optional
from collections import deque

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

def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
    """Inorder traversal: Left -> Root -> Right.
    
    Time: O(n), Space: O(h) where h is height
    """
    result = []
    stack = []
    current = root
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        result.append(current.val)
        current = current.right
    
    return result

def preorder_traversal(root: Optional[TreeNode]) -> List[int]:
    """Preorder traversal: Root -> Left -> Right.
    
    Time: O(n), Space: O(h)
    """
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
    """Level order traversal (BFS).
    
    Time: O(n), Space: O(n)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

def zigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """Zigzag level order traversal.
    
    Time: O(n), Space: O(n)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        current_level = deque()
        
        for _ in range(level_size):
            node = queue.popleft()
            
            if left_to_right:
                current_level.append(node.val)
            else:
                current_level.appendleft(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(list(current_level))
        left_to_right = not left_to_right
    
    return result

Binary Search Trees

class BST:
    """Binary Search Tree implementation."""
    
    def __init__(self):
        self.root = None
    
    def insert(self, val: int) -> None:
        self.root = self._insert(self.root, val)
    
    def _insert(self, node: Optional[TreeNode], val: int) -> TreeNode:
        if not node:
            return TreeNode(val)
        
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        
        return node
    
    def search(self, val: int) -> bool:
        return self._search(self.root, val)
    
    def _search(self, node: Optional[TreeNode], val: int) -> bool:
        if not node:
            return False
        
        if val == node.val:
            return True
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)
    
    def delete(self, val: int) -> None:
        self.root = self._delete(self.root, val)
    
    def _delete(self, node: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not node:
            return None
        
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # Node with only one child or no child
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            
            # Node with two children: Get inorder successor
            node.val = self._min_value(node.right)
            node.right = self._delete(node.right, node.val)
        
        return node
    
    def _min_value(self, node: TreeNode) -> int:
        current = node
        while current.left:
            current = current.left
        return current.val
    
    def is_valid_bst(self) -> bool:
        return self._validate(self.root, float('-inf'), float('inf'))
    
    def _validate(self, node: Optional[TreeNode], min_val: float, max_val: float) -> bool:
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (self._validate(node.left, min_val, node.val) and
                self._validate(node.right, node.val, max_val))

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """Find LCA of two nodes in BST.
    
    Time: O(h), Space: O(h)
    """
    current = root
    
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current
    
    return None

def kth_smallest(root: TreeNode, k: int) -> int:
    """Find kth smallest element in BST.
    
    Time: O(k + h), Space: O(h)
    """
    stack = []
    current = root
    
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        k -= 1
        
        if k == 0:
            return current.val
        
        current = current.right
    
    return -1

Graph Algorithms

from typing import List, Dict, Set
from collections import defaultdict, deque

class Graph:
    """Graph representation using adjacency list."""
    
    def __init__(self, directed: bool = False):
        self.graph = defaultdict(list)
        self.directed = directed
        self.vertices = set()
    
    def add_edge(self, u: int, v: int, weight: int = 1):
        self.graph[u].append((v, weight))
        self.vertices.add(u)
        self.vertices.add(v)
        
        if not self.directed:
            self.graph[v].append((u, weight))
    
    def bfs(self, start: int) -> List[int]:
        """Breadth-first search.
        
        Time: O(V + E), Space: O(V)
        """
        visited = {start}
        queue = deque([start])
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            for neighbor, _ in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return result
    
    def dfs(self, start: int) -> List[int]:
        """Depth-first search (iterative).
        
        Time: O(V + E), Space: O(V)
        """
        visited = {start}
        stack = [start]
        result = []
        
        while stack:
            vertex = stack.pop()
            result.append(vertex)
            
            for neighbor, _ in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
        
        return result
    
    def has_path(self, source: int, destination: int) -> bool:
        """Check if path exists between source and destination."""
        if source == destination:
            return True
        
        visited = {source}
        queue = deque([source])
        
        while queue:
            vertex = queue.popleft()
            
            for neighbor, _ in self.graph[vertex]:
                if neighbor == destination:
                    return True
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return False
    
    def detect_cycle(self) -> bool:
        """Detect cycle in directed graph using DFS."""
        WHITE, GRAY, BLACK = 0, 1, 2
        color = {v: WHITE for v in self.vertices}
        
        def dfs_cycle(vertex: int) -> bool:
            color[vertex] = GRAY
            
            for neighbor, _ in self.graph[vertex]:
                if color[neighbor] == GRAY:
                    return True
                if color[neighbor] == WHITE and dfs_cycle(neighbor):
                    return True
            
            color[vertex] = BLACK
            return False
        
        for vertex in self.vertices:
            if color[vertex] == WHITE:
                if dfs_cycle(vertex):
                    return True
        
        return False

def topological_sort_kahn(graph: Graph) -> List[int]:
    """Topological sort using Kahn's algorithm (BFS).
    
    Time: O(V + E), Space: O(V)
    """
    in_degree = defaultdict(int)
    
    for vertex in graph.vertices:
        for neighbor, _ in graph.graph[vertex]:
            in_degree[neighbor] += 1
    
    queue = deque([v for v in graph.vertices if in_degree[v] == 0])
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        for neighbor, _ in graph.graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != len(graph.vertices):
        raise ValueError("Graph has a cycle")
    
    return result

def course_schedule(num_courses: int, prerequisites: List[List[int]]) -> bool:
    """Determine if all courses can be finished (cycle detection).
    
    Time: O(V + E), Space: O(V)
    """
    graph = defaultdict(list)
    in_degree = [0] * num_courses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    count = 0
    
    while queue:
        vertex = queue.popleft()
        count += 1
        
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return count == num_courses

# Test cases
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)

print(graph.bfs(0))  # [0, 1, 2, 3]
print(graph.dfs(0))  # [0, 2, 3, 1]
print(course_schedule(2, [[1, 0]]))  # True

Binary Tree Construction

def build_tree_from_preorder_inorder(
    preorder: List[int], inorder: List[int]
) -> Optional[TreeNode]:
    """Construct binary tree from preorder and inorder traversals.
    
    Time: O(n), Space: O(n)
    """
    if not preorder or not inorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    mid = inorder.index(root_val)
    
    root.left = build_tree_from_preorder_inorder(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree_from_preorder_inorder(preorder[mid + 1:], inorder[mid + 1:])
    
    return root

def serialize(root: Optional[TreeNode]) -> str:
    """Serialize binary tree to string."""
    if not root:
        return "null"
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("null")
    
    return ','.join(result)

def deserialize(data: str) -> Optional[TreeNode]:
    """Deserialize string to binary tree."""
    if data == "null":
        return None
    
    values = data.split(',')
    root = TreeNode(int(values[0]))
    queue = deque([root])
    i = 1
    
    while queue and i < len(values):
        node = queue.popleft()
        
        if values[i] != "null":
            node.left = TreeNode(int(values[i]))
            queue.append(node.left)
        i += 1
        
        if i < len(values) and values[i] != "null":
            node.right = TreeNode(int(values[i]))
            queue.append(node.right)
        i += 1
    
    return root

def is_symmetric(root: Optional[TreeNode]) -> bool:
    """Check if binary tree is symmetric.
    
    Time: O(n), Space: O(h)
    """
    def is_mirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        
        return (t1.val == t2.val and
                is_mirror(t1.left, t2.right) and
                is_mirror(t1.right, t2.left))
    
    return is_mirror(root, root) if root else True

# Test cases
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
tree = build_tree_from_preorder_inorder(preorder, inorder)
print(level_order_traversal(tree))  # [[3], [9, 20], [15, 7]]

serialized = serialize(tree)
print(serialized)  # "3,9,20,null,null,15,7"

Follow-Up Questions

1. How would you find the diameter of a binary tree?

2. Explain the difference between BFS and DFS for graph problems.

3. How do you handle weighted graphs in shortest path algorithms?

4. When would you use Dijkstra's algorithm vs Bellman-Ford?

5. How do you find bridges and articulation points in a graph?