Tree and Graph Interview Questions and Answers

16 questions

What is the difference between a binary tree and a binary search tree?
A binary tree is any tree with at most two children per node. A BST adds an order: left subtree smaller, right subtree larger, so search, insert and delete follow one path, O(h). Balanced, h is O(log n); sorted inserts make a plain BST a list.

Follow-up: validate a BST? Pass down the allowed (low, high) range; comparing a node only with its children is wrong. Try inserts and searches on a BST.
Practice it: Validate Binary Search Tree, Range Sum of BST
What are full, complete, perfect and balanced binary trees?
They are rules about a binary tree's shape. Full: every node has 0 or 2 children. Complete: every level is full except possibly the last, filled from the left. Perfect: every internal node has two children and all leaves are on one level, so height h (in edges) means 2^(h+1) - 1 nodes. Balanced: subtree heights differ by at most 1 everywhere, so height is O(log n). A heap is complete, which is why it fits in an array. See a binary tree built node by node.
Practice it: Maximum Depth of Binary Tree

What are inorder, preorder and postorder traversals?

They are depth-first orders that differ in when the node itself is visited: preorder is node, left, right; inorder is left, node, right; postorder is left, right, node.

Python

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

# 4 has children 2 and 6; 2 has 1 and 3; 6 has 5 and 7
root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

def preorder(n):
    return [n.val] + preorder(n.left) + preorder(n.right) if n else []

def postorder(n):
    return postorder(n.left) + postorder(n.right) + [n.val] if n else []

print("inorder:  ", inorder(root))
print("preorder: ", preorder(root))
print("postorder:", postorder(root))

Inorder on a BST gives sorted values. Preorder copies or serializes a tree; postorder computes from the children up, such as heights.

Practice it: Invert Binary Tree, Symmetric Tree

In what order does a preorder traversal visit this five-node tree?

Python

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

root = Node(1, Node(2, Node(4), Node(5)), Node(3))

def preorder(n):
    if not n:
        return []
    return [n.val] + preorder(n.left) + preorder(n.right)

print(preorder(root))

Preorder visits a node before its subtrees: 1, then the left subtree (2, 4, 5), then 3. [4, 2, 5, 1, 3] is inorder, [4, 5, 2, 3, 1] postorder and [1, 2, 3, 4, 5] level order.

How do you find the height (maximum depth) of a binary tree?
A node's height is 1 plus the larger of its children's heights, and an empty tree has height 0. Each node is visited once: O(n) time, O(h) stack.
Python
class Node: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right def height(node): if node is None: return 0 return 1 + max(height(node.left), height(node.right)) root = Node(3, Node(9), Node(20, Node(15), Node(7, Node(1)))) print(height(root))
Ask whether height counts nodes or edges; the two definitions differ by one.
Practice it: Maximum Depth of Binary Tree, Diameter of Binary Tree

How do you find the lowest common ancestor of two nodes in a binary tree or a BST?

The LCA of p and q is the deepest node with both in its subtree (a node is its own descendant). In a BST, walk down: both values smaller, go left; both larger, go right; otherwise this node is the LCA, in O(h).

Python

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

def lca_bst(root, p, q):
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val
    return None

def lca_tree(node, p, q):   # any binary tree, p and q both present
    if node is None or node.val in (p, q):
        return node
    left = lca_tree(node.left, p, q)
    right = lca_tree(node.right, p, q)
    return node if left and right else left or right

# 6 has children 2 and 8; 2 has 0 and 4; 8 has 7 and 9
root = Node(6, Node(2, Node(0), Node(4)), Node(8, Node(7), Node(9)))
print(lca_bst(root, 2, 8), lca_bst(root, 0, 4), lca_bst(root, 2, 4))
print(lca_tree(root, 0, 4).val, lca_tree(root, 7, 9).val)

A plain binary tree has no order, so lca_tree searches both sides in O(n). The BST trap: p itself can be the answer, as lca_bst(root, 2, 4) returns 2.

Practice it: Lowest Common Ancestor of a BST

How do you do a level order traversal of a binary tree?

Use a queue: record its length, pop exactly that many nodes and push their children; that is one level. O(n) time, O(w) space for the widest level w.

Python

from collections import deque

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

def level_order(root):
    if not root:
        return []
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

root = Node(3, Node(9), Node(20, Node(15), Node(7)))
print(level_order(root))

The same loop gives right side view (the last node of each level) and zigzag order.

Practice it: Binary Tree Level Order Traversal

What is the difference between BFS and DFS, and when do you use each?
BFS explores level by level with a queue; DFS follows one path as deep as it can before backtracking, with recursion or a stack. Both are O(V + E). BFS finds the fewest steps when every step costs the same; DFS does not, but suits islands, topological sort, cycles and backtracking, and holds only the current path in memory. Watch BFS spread out level by level.
Practice it: Rotting Oranges, Word Ladder

In what order does BFS from A visit a graph where B and C share a neighbor?

Python

from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
seen = {"A"}
order = []
q = deque(["A"])
while q:
    node = q.popleft()
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            seen.add(nxt)
            q.append(nxt)
print(" ".join(order))

BFS finishes A's neighbors, B and C, before going deeper, then visits D and E: A B C D E. A B D C E is the DFS order. Marking nodes seen when enqueued stops D being queued twice.

Practice it: Find if Path Exists in Graph

How do you represent a graph: adjacency list or adjacency matrix?
An adjacency list stores each node's neighbors, O(V + E) space; an adjacency matrix is a V × V grid where m[u][v] says whether the edge exists, O(V²) space but an O(1) edge check. Default to a list, since most graphs are sparse; in Python, a dict of lists:
Python
from collections import defaultdict edges = [(0, 1), (0, 2), (1, 2), (2, 3)] graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) # drop this line for a directed graph print(dict(graph))
Practice it: Find if Path Exists in Graph, Number of Provinces

How do you count the number of islands in a grid?

Scan every cell; on unvisited land, count an island and flood fill from it, marking connected land visited. O(rows × cols).

Python

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def fill(r, c):
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
                continue
            if grid[r][c] == "0":
                continue
            seen.add((r, c))
            stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                fill(r, c)
    return count

grid = [
    "11000",
    "11000",
    "00100",
    "00011",
]
print(num_islands(grid))

The fill uses an explicit stack because recursive DFS on a 1000 × 1000 land grid would pass Python's recursion limit.

Practice it: Number of Islands, Flood Fill, Rotting Oranges

How do you detect a cycle in a directed graph, and what is topological sort?

A topological order lists a directed graph's nodes so every edge goes from earlier to later, like prerequisites before courses. It exists exactly when there is no cycle, so computing it detects cycles. Kahn's algorithm repeatedly removes nodes with no incoming edges, O(V + E):

Python

from collections import deque

def topo_order(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:          # u must come before v
        graph[u].append(v)
        indegree[v] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else None   # None: a cycle

print(topo_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))
print(topo_order(3, [(0, 1), (1, 2), (2, 0)]))

The DFS version colors nodes white, gray and black; reaching a gray node means a cycle. See topological sort run on a graph.

Practice it: Course Schedule, Alien Dictionary

How does Dijkstra's algorithm work, and when does it fail?

Dijkstra finds shortest paths from one source when no edge weight is negative. Pop the closest node from a min heap and relax its edges. O((V + E) log V) with a binary heap.

Python

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                  # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": [],
}
print(dijkstra(graph, "A"))

Negative weights break it, since a node popped as final could later get a shorter path; use Bellman-Ford, O(VE). With equal weights, BFS is enough. See Dijkstra relax edges step by step.

Practice it: Network Delay Time, Swim in Rising Water

What is a trie, and when is it better than a hash set?

A trie stores strings character by character: each node maps a character to a child, and a flag marks a word's end. Insert, search and "any word with this prefix?" are O(L) for length L; a hash set cannot answer the prefix query without scanning.

Python

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True   # end of a word

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and "$" in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

t = Trie()
for w in ["code", "coder", "coddy"]:
    t.insert(w)
print(t.search("cod"), t.starts_with("cod"), t.search("coder"))

The cost is memory, one node per character of every distinct prefix. Watch words being inserted into a trie.

Practice it: Implement Trie (Prefix Tree), Word Search

What is union find (disjoint set union), and where is it used?

Union find keeps disjoint sets: find(x) returns x's representative, union(a, b) merges two sets. With path compression and union by size, both are nearly O(1) amortized.

Python

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False      # already connected: this edge closes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

d = DSU(5)
for a, b in [(0, 1), (1, 2), (3, 4)]:
    d.union(a, b)
groups = len({d.find(i) for i in range(5)})
print(groups, d.union(0, 2))

Use it for connected components, undirected cycles and Kruskal's MST. It cannot split a set, so edge deletions do not fit.

Practice it: Number of Provinces

What is a minimum spanning tree, and how do Kruskal's and Prim's algorithms differ?

A minimum spanning tree of a connected, undirected, weighted graph is the V - 1 edges that connect every vertex at the lowest total weight. Kruskal sorts edges and adds each that closes no cycle, using union find, O(E log E); Prim grows one tree by the lightest leaving edge, O(E log V) with a heap.

Python

def kruskal(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total, used = 0, []
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:          # skip edges that would close a cycle
            parent[ru] = rv
            total += w
            used.append((u, v, w))
    return total, used

edges = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)]   # (weight, u, v)
print(kruskal(4, edges))

An MST minimizes total weight, not distance from a source. See Kruskal's algorithm pick edges.

What is the difference between a binary tree and a binary search tree?

What are full, complete, perfect and balanced binary trees?

What are inorder, preorder and postorder traversals?

In what order does a preorder traversal visit this five-node tree?

How do you find the height (maximum depth) of a binary tree?

How do you find the lowest common ancestor of two nodes in a binary tree or a BST?

How do you do a level order traversal of a binary tree?

What is the difference between BFS and DFS, and when do you use each?

In what order does BFS from A visit a graph where B and C share a neighbor?

How do you represent a graph: adjacency list or adjacency matrix?

How do you count the number of islands in a grid?

How do you detect a cycle in a directed graph, and what is topological sort?

How does Dijkstra's algorithm work, and when does it fail?

What is a trie, and when is it better than a hash set?

What is union find (disjoint set union), and where is it used?

What is a minimum spanning tree, and how do Kruskal's and Prim's algorithms differ?

Learn to code with Coddy