Navigation

DSA interview 12 min read

Top Tree & Graph Interview Questions with Solutions (C++, Java, JS, Python)

This page covers the tree and graph interview questions that interviewers love because they test recursion, BFS/DFS, and traversal order all at once. Each entry gives the problem, the approach, the complexity, and a full C++/Java/JavaScript/Python solution via the switcher. For the underlying concepts, see trees introduction and graphs introduction.

Mental model: Almost every tree problem is a recursive DFS that combines results from the left and right child. Almost every graph problem is a BFS/DFS over an adjacency structure, with a visited set to avoid cycles. Master those two shapes and these questions become variations on a theme.

The tree solutions assume a node with a val and left/right children, shown in each snippet.

1. Maximum Depth of a Binary Tree

Question. Return the number of nodes along the longest path from the root down to a leaf.

Approach. Post-order recursion: the depth of a node is 1 plus the larger of its children’s depths. An empty subtree has depth 0.

Complexity. O(n) time, O(h) space for the call stack (h = height).

#include <algorithm>
struct TreeNode { int val; TreeNode* left; TreeNode* right; };

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

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

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

// node: { val, left, right }
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

# node has .val, .left, .right
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

2. Invert a Binary Tree

Question. Mirror a binary tree so every node’s left and right children are swapped.

Approach. Swap children at each node, then recurse into both subtrees.

Complexity. O(n) time, O(h) space.

#include <algorithm>

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    std::swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [root.right, root.left];
  invertTree(root.left);
  invertTree(root.right);
  return root;
}

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

3. Validate a Binary Search Tree

Question. Decide whether a binary tree is a valid BST: every left value is strictly less, every right value strictly greater, recursively.

Approach. Carry a valid (low, high) range down the tree. Each node must lie strictly inside its range; the left child tightens the upper bound, the right child tightens the lower bound. (Checking only parent vs child is the classic wrong answer.)

Complexity. O(n) time, O(h) space.

#include <climits>

bool validate(TreeNode* node, long lo, long hi) {
    if (!node) return true;
    if (node->val <= lo || node->val >= hi) return false;
    return validate(node->left, lo, node->val) &&
           validate(node->right, node->val, hi);
}
bool isValidBST(TreeNode* root) {
    return validate(root, LONG_MIN, LONG_MAX);
}

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
boolean validate(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return validate(node.left, lo, node.val) &&
           validate(node.right, node.val, hi);
}

function isValidBST(root, lo = -Infinity, hi = Infinity) {
  if (!root) return true;
  if (root.val <= lo || root.val >= hi) return false;
  return isValidBST(root.left, lo, root.val) &&
         isValidBST(root.right, root.val, hi);
}

def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    if not root:
        return True
    if not (lo < root.val < hi):
        return False
    return is_valid_bst(root.left, lo, root.val) and \
           is_valid_bst(root.right, root.val, hi)

4. Binary Tree Level-Order Traversal

Question. Return the node values level by level, top to bottom (a list of lists).

Approach. BFS with a queue. Process the queue one full level at a time by recording its size before the inner loop.

Complexity. O(n) time, O(n) space.

#include <vector>
#include <queue>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    if (!root) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        std::vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

import java.util.*;

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        res.add(level);
    }
    return res;
}

function levelOrder(root) {
  const res = [];
  if (!root) return res;
  let queue = [root];
  while (queue.length) {
    const level = [], next = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    res.push(level);
    queue = next;
  }
  return res;
}

from collections import deque

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

See level-order traversal for more BFS patterns.

5. Lowest Common Ancestor of a Binary Tree

Question. Given two nodes p and q, return their lowest common ancestor — the deepest node that has both in its subtree.

Approach. Recurse. If the current node is null, p, or q, return it. If p and q are found in different subtrees, the current node is the LCA; otherwise return whichever side found something.

Complexity. O(n) time, O(h) space.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Deeper coverage on the lowest common ancestor page.

6. Number of Islands

Question. Given a grid of '1' (land) and '0' (water), count the islands. Land connects horizontally and vertically.

Approach. Scan the grid; on each unvisited land cell, flood-fill with DFS, sinking the whole island to '0', and increment the count. Each cell is visited once.

Complexity. O(rows · cols) time, O(rows · cols) space (recursion in the worst case).

#include <vector>

void sink(std::vector<std::vector<char>>& g, int r, int c) {
    if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != '1')
        return;
    g[r][c] = '0';
    sink(g, r + 1, c); sink(g, r - 1, c);
    sink(g, r, c + 1); sink(g, r, c - 1);
}
int numIslands(std::vector<std::vector<char>>& g) {
    int count = 0;
    for (int r = 0; r < (int)g.size(); r++)
        for (int c = 0; c < (int)g[0].size(); c++)
            if (g[r][c] == '1') { count++; sink(g, r, c); }
    return count;
}

int numIslands(char[][] g) {
    int count = 0;
    for (int r = 0; r < g.length; r++)
        for (int c = 0; c < g[0].length; c++)
            if (g[r][c] == '1') { count++; sink(g, r, c); }
    return count;
}
void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';
    sink(g, r + 1, c); sink(g, r - 1, c);
    sink(g, r, c + 1); sink(g, r, c - 1);
}

function numIslands(g) {
  let count = 0;
  const sink = (r, c) => {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] !== "1") return;
    g[r][c] = "0";
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  };
  for (let r = 0; r < g.length; r++)
    for (let c = 0; c < g[0].length; c++)
      if (g[r][c] === "1") { count++; sink(r, c); }
  return count;
}

def num_islands(g):
    if not g:
        return 0
    rows, cols = len(g), len(g[0])

    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or g[r][c] != "1":
            return
        g[r][c] = "0"
        sink(r + 1, c); sink(r - 1, c)
        sink(r, c + 1); sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if g[r][c] == "1":
                count += 1
                sink(r, c)
    return count

7. Course Schedule (Cycle Detection)

Question. Given numCourses and prerequisite pairs [a, b] (take b before a), can you finish all courses? This is asking whether the directed graph is acyclic.

Approach. Topological sort via Kahn’s algorithm. Build an adjacency list and in-degree counts; repeatedly remove nodes with in-degree 0. If you process every course, there is no cycle.

Complexity. O(V + E) time, O(V + E) space.

#include <vector>
#include <queue>

bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
    std::vector<std::vector<int>> adj(numCourses);
    std::vector<int> indeg(numCourses, 0);
    for (auto& p : prerequisites) { adj[p[1]].push_back(p[0]); indeg[p[0]]++; }
    std::queue<int> q;
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.push(i);
    int done = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        done++;
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    return done == numCourses;
}

import java.util.*;

boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[numCourses];
    for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.add(i);
    int done = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        done++;
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
    }
    return done == numCourses;
}

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) queue.push(i);
  let done = 0;
  while (queue.length) {
    const u = queue.shift();
    done++;
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v);
  }
  return done === numCourses;
}

from collections import deque

def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(num_courses) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft()
        done += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == num_courses

Pitfall: On deep trees or large grids, recursive DFS can blow the call stack. Mention this trade-off in interviews and offer an explicit stack or BFS as the iterative alternative.

Keep practicing

These seven span the essential tree/graph toolkit: recursive DFS that combines child results, range-passing validation, BFS by level, flood fill, and topological sort. Drill more on the tree exercises and graph exercises, then finish with dynamic programming interview questions.