Tree and Graph Traversal Questions

Comprehensive mastery of tree and graph traversal algorithms, representations, and common interview problem patterns. Understand graph models and representation choices including adjacency lists versus adjacency matrices and trade offs based on sparsity and density, as well as properties such as directed versus undirected and weighted versus unweighted edges. Know visited state management to avoid cycles and techniques for cycle detection. Implement breadth first search and depth first search in both recursive and iterative forms, understand when to use a queue versus a stack, and analyze time and space complexity. Apply traversals to problems such as shortest path in unweighted graphs, connected component detection, topological sort for dependency ordering, cycle detection, path existence, and island counting. For trees, master traversal orders including in order, pre order, post order, and level order with both recursive and iterative implementations, including explicit stack based approaches and constant space approaches where relevant. Practice tree specific problems such as lowest common ancestor, path sum, tree serialization and deserialization, validating binary search trees, balancing and reconstruction of trees from traversal sequences, and converting between tree and graph formulations. Emphasize clean code, correctness, handling edge cases such as empty or skewed structures, recursion base cases and depth limits, and explaining trade offs between recursion and iterative solutions with respect to performance and memory.

EasyTechnical

27 practiced

Given an undirected graph represented as an adjacency list, implement count_connected_components(graph) in Python that returns the number of connected components. Graph nodes can be any hashable type. Ensure you handle empty graphs and disconnected nodes efficiently using BFS or DFS.

Sample Answer

**Approach (brief)**

Use iterative DFS (stack) or BFS to traverse each component. Track visited nodes in a set. For every node not visited, start a traversal and increment component count. This handles empty graphs and isolated nodes (nodes with empty neighbor lists).

**Code (Python)**

python

def count_connected_components(graph):
    """
    graph: dict-like adjacency list mapping node -> iterable of neighbors
    returns: int number of connected components
    """
    if not graph:
        return 0

    visited = set()
    components = 0

    for node in graph:
        if node in visited:
            continue
        components += 1
        # iterative DFS
        stack = [node]
        while stack:
            n = stack.pop()
            if n in visited:
                continue
            visited.add(n)
            # push neighbors; tolerate neighbors not listed as keys
            for nei in graph.get(n, []):
                if nei not in visited:
                    stack.append(nei)
    return components

**Key concepts**

- Uses O(V + E) time: visits each node and edge once.- Space O(V) for visited and stack.- Handles nodes that appear only as neighbors by using graph.get(n, []) and assumes all nodes of interest are keys in graph; if some nodes only appear as neighbors, include them as keys or preprocess to add them.

**Edge cases**

- Empty graph -> 0- Isolated nodes -> counted correctly (neighbors = [])- Nodes referenced only as neighbors -> preprocess to include them if needed

**Alternative**

Use BFS (collections.deque) or recursive DFS (watch recursion depth for large graphs).

EasyTechnical

32 practiced

Implement iterative inorder traversal of a binary tree in Python without recursion. The TreeNode structure has 'val', 'left', and 'right' attributes. Your function should return a list of node values in inorder. Ensure your solution handles empty trees and very skewed trees without causing recursion depth issues.

Sample Answer

**Approach**Use an explicit stack to simulate recursion: walk left as far as possible pushing nodes, then visit node, then go right. This handles empty and skewed trees without recursion depth limits.

**Code**

python

# Python iterative inorder traversal
def inorder_traversal(root):
    result = []
    stack = []
    current = root

    # Continue until no nodes left to visit
    while current or stack:
        # Reach the left most Node of the current Node
        while current:
            stack.append(current)
            current = current.left

        # Current must be None at this point
        node = stack.pop()
        result.append(node.val)         # Visit
        current = node.right            # Explore right subtree

    return result

**Key concepts**- Stack holds ancestors waiting to be visited.- Works for empty trees (returns []) and skewed trees (stack depth equals tree height but avoids recursion limits).

**Complexity**- Time: O(n) — each node pushed/popped once.- Space: O(h) where h is tree height (O(n) worst-case for skewed tree).

**Alternatives**- Morris traversal (O(1) space) but modifies tree temporarily; use when minimizing space is critical.

HardTechnical

36 practiced

You are building graph-query APIs used by frontend: getFriendsAtDistance(user, k), mutualConnections(u,v), and recommendConnections(user). For a massive social graph, design the traversal algorithms, caching/precomputation strategies (e.g., 1-hop and 2-hop caches, partial indexes), synchronous vs asynchronous execution trade-offs, TTL and consistency considerations, and monitoring metrics you would track to ensure latency and correctness.

Sample Answer

**Clarify requirements & constraints**- Read SLA: p50/p95 latency targets, staleness tolerance for recommendations, QPS and graph size (billions of nodes, tens of billions of edges), write rate.

**Traversal algorithms**- getFriendsAtDistance(user,k): do BFS limited to k with pruning by max frontier size; use adjacency lists sharded by node-id. For k<=2 prefer edge-lookup + set-ops; for k>2 stream frontier with early stop.- mutualConnections(u,v): intersect 1-hop sets (use smaller-first, bloom filter or sorted-merge).- recommendConnections(user): compute 2-hop neighbors weighted by common neighbors, degree-normalization, filter by signals (interaction recency).

**Caching & precomputation**- Materialize 1-hop adjacency for all users (hot key in memory / distributed cache like Redis Cluster).- Partial 2-hop caches for high-degree or active users, updated asynchronously.- Compact partial index: store top-N 2-hop candidates per user (for recommendConnections).- Use compressed bitmaps (Roaring) for adjacency to speed set ops and save memory.

**Sync vs async**- Strongly consistent 1-hop reads synchronous on write-path (writes update DB then invalidate cache). 2-hop and recommendations generated asynchronously with eventual consistency; surface cached result immediately, kick off background refresh if stale.

**TTL & consistency**- 1-hop TTL short (seconds) with write invalidation. 2-hop / recommendations TTL longer (minutes–hours) depending on staleness tolerance. Use write logs/CDC to trigger targeted recompute for impacted precomputations.

**Monitoring & metrics**- Latency p50/p95/p99 per API; cache hit ratio (1-hop, 2-hop); freshness (time-since-last-compute); correctness sampling: run golden queries offline and compare top-k precision/recall; error rates/timeouts; cardinality distributions of frontiers; background job lag and fail rates.

**Trade-offs & notes**- Precompute reduces latency but increases storage and complexity; partial indexes focus on heavy hitters. Use bloom/bitmap for fast membership; ensure throttling for very high-degree nodes and provide degraded responses (sampled neighbors) to meet SLAs.

HardTechnical

38 practiced

Design a compact serialization and streaming protocol for an N-ary tree that supports encoding and decoding in constant auxiliary memory proportional to encoding buffer (i.e., you cannot buffer the entire tree). Provide Python pseudocode for serialize and a streaming deserialize that can resume after partial reads. Discuss how to represent unknown child counts and how to handle backpressure when writing to the network.

Sample Answer

**High-level approach**- Use a compact binary framing with node payload length + children encoding using start/stop markers so you don't need to pre-count children.- Streaming property: serializer writes nodes in pre-order using a small explicit stack; deserializer processes bytes incrementally and maintains only the parsing stack and partial node buffers (aux proportional to current buffer).

**Wire format**- Node frame: [B1: tag][B?: payload_len (varint)][payload bytes][child marker stream]- Child markers: use single-byte tokens: 0x01 = child-start, 0x00 = child-end. After payload, emit 0x01 then child subtree(s) repeated, and terminate children with 0x00.- This represents unknown child counts naturally — you end with 0x00.

**Serializer (Python pseudocode)**

python

# preorder streaming serializer, yields bytes
def serialize(root):
    stack = [root]
    while stack:
        node = stack.pop()
        payload = node.value.encode('utf-8')
        # header: tag 0xA0, varint length
        yield bytes([0xA0]) + encode_varint(len(payload)) + payload
        if node.children:
            # open child list marker
            yield bytes([0x01])
            # push end marker context then children reversed for preorder
            # children are written next; after last child, writer must emit 0x00
            stack.append(None)  # sentinel for child-end
            for c in reversed(node.children):
                stack.append(c)
        else:
            # emit empty-child list marker then close immediately
            yield bytes([0x01, 0x00])
        # handle child-end sentinel
        while stack and stack[-1] is None:
            stack.pop()
            yield bytes([0x00])

**Streaming deserializer (resume-able)**

python

def deserialize_stream(byte_iter):
    buf = bytearray()
    stack = []  # parents awaiting children
    partial = None
    for chunk in byte_iter:
        buf.extend(chunk)
        while True:
            if len(buf) < 1: break
            b = buf[0]
            if b == 0xA0:
                # need varint and payload
                n, vlen = try_decode_varint(buf, 1)
                if n is None: break
                start = 1 + vlen
                if len(buf) < start + n: break
                payload = bytes(buf[start:start+n]).decode('utf-8')
                node = Node(payload, [])
                buf[:] = buf[start+n:]
                # attach to parent if exists
                if stack: stack[-1].children.append(node)
                else: root = node
                # push this node as current parent; next token should be 0x01
                stack.append(node)
            elif b == 0x01:
                # child-list start
                buf.pop(0)
            elif b == 0x00:
                # child-list end: pop parent
                buf.pop(0)
                stack.pop()
            else:
                raise ValueError('bad token')
    return root  # None if incomplete; caller can resume by feeding more chunks

**Why this works**- Markers let you avoid precomputing child count; decoder can stream and resume because state equals parse stack + residual buffer.- Memory equals current payload being read + stack of ancestors (O(tree height), not whole tree).

**Backpressure**- Serializer yields bytes, caller is responsible for network write. For blocking sockets use non-blocking writes or async awaits: - On full socket buffer, stop pulling more from serializer and backpressure upstream (e.g., await drain()). - In async frameworks (asyncio), use flow-control: await writer.drain() when write() returns immediately but buffer is full.- Keep serialized chunk sizes bounded (e.g., 4KB frames) so you never produce unbounded data when network is slow.

**Edge cases / notes**- Use varint for lengths to be compact.- Protect against deeply recursive/evil inputs by limiting stack depth.- Include checksums or version tag if protocol evolves.

HardTechnical

37 practiced

Implement a Python function that detects a cycle in a directed graph and, if a cycle exists, returns one cycle as a list of nodes in order. The graph is given as an adjacency list and may have multiple components and parallel edges. Your solution should run in O(V+E) time and handle self-loops properly. Explain how you reconstruct the cycle using the recursion stack or parent pointers.

Sample Answer

**Approach (brief)**

Use DFS with 3-color marking (0=unvisited,1=visiting,2=done). When DFS finds an edge to a visiting node, that indicates a back edge -> cycle. Reconstruct cycle by following parent pointers from current node back to the target node on the recursion stack.

**Code (Python)**

python

def find_cycle(adj):
    n = len(adj)
    color = [0]*n           # 0 unvisited,1 visiting,2 done
    parent = [-1]*n
    cycle = []

    def dfs(u):
        color[u] = 1
        for v in adj[u]:
            if color[v] == 0:
                parent[v] = u
                if dfs(v):
                    return True
            elif color[v] == 1:
                # found back edge u -> v, reconstruct cycle
                cur = u
                cycle.append(v)
                while cur != v and cur != -1:
                    cycle.append(cur)
                    cur = parent[cur]
                cycle.reverse()
                return True
        color[u] = 2
        return False

    for i in range(n):
        if color[i] == 0:
            if dfs(i):
                return cycle
    return None

**Explanation & reasoning**

- parent[] records the recursion stack path; on back edge u->v we walk parents from u to v to collect nodes in order.- Handles self-loops: if edge u->u, color[u]==1 triggers immediate cycle [u].- Parallel edges naturally handled — any back edge detected triggers reconstruction.- Time: O(V+E) since each edge and node processed constant times. Space: O(V) for color/parent/recursion.

Unlock Full Question Bank

Get access to hundreds of Tree and Graph Traversal interview questions and detailed answers.

Join thousands of developers preparing for their dream job.