Trees & Graphs Basics Questions

Understand binary trees, binary search trees, and basic graph concepts. Know tree traversal methods: in-order, pre-order, post-order, and level-order (BFS). Practice DFS and BFS implementations. Know the difference between directed and undirected graphs. Solve medium-difficulty tree and graph problems.

MediumTechnical

20 practiced

Implement iterative inorder traversal of a binary tree in Python using an explicit stack (no recursion). Explain time and space complexity and compare to recursive approach. Optionally describe Morris inorder traversal for O(1) space and mention when pointer mutation is acceptable.

Sample Answer

To perform iterative inorder traversal (Left, Node, Right) without recursion, use an explicit stack to simulate the call stack: push left children until null, then process node, then go right.

python

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

def inorder_iterative(root):
    """
    Iterative inorder traversal using an explicit stack.
    Yields node values in-order.
    """
    stack = []
    current = root

    while current or stack:
        # Reach the leftmost node of current
        while current:
            stack.append(current)
            current = current.left
        # current is None here; pop from stack
        node = stack.pop()
        yield node.val
        # visit right subtree
        current = node.right

Key points:- We push nodes while traversing left, then pop to visit, then switch to right.- Time complexity: O(n) — each node visited/pushed/popped a constant number of times.- Space complexity: O(h) where h is tree height (O(n) worst-case skewed, O(log n) for balanced).

Comparison to recursion:- Recursive inorder uses implicit call stack with O(h) space and similar O(n) time. Iterative gives finer control (e.g., streaming results) and avoids recursion depth limits.

Morris inorder (threaded traversal) achieves O(1) extra space by temporarily modifying right pointers to create threads to predecessors and restoring them after use. Use Morris when memory is critical and you can safely mutate pointers (e.g., temporary structures, single-threaded contexts). Avoid Morris when tree nodes are shared, immutable, or when pointer mutation could break other references or concurrent access.

EasyTechnical

22 practiced

Given a graph represented as an adjacency list (a dict mapping node -> list of neighbors), implement a recursive depth-first search in Python that returns the set or list of nodes reachable from a given source. Carefully handle the visited set to avoid infinite recursion and mention complexity.

Sample Answer

A simple recursive DFS visits neighbors and records visited nodes to avoid infinite recursion. We'll return a set of reachable nodes.

python

def dfs_recursive(graph, src, visited=None):
    """
    Recursive DFS that returns a set of nodes reachable from src.
    graph: dict[node] -> list of neighbor nodes
    src: starting node
    visited: set used internally to track visited nodes (None for external calls)
    """
    if visited is None:
        visited = set()
    # Mark current node visited
    visited.add(src)
    # Recurse on unvisited neighbors
    for nbr in graph.get(src, []):
        if nbr not in visited:
            dfs_recursive(graph, nbr, visited)
    return visited

Key points:- visited is passed down the recursive calls so each node is processed at most once, preventing infinite recursion on cycles.- Using graph.get(src, []) handles missing nodes gracefully.

Complexity:- Time: O(V + E) — each node and edge explored once.- Space: O(V) for visited plus O(H) recursion stack where H is the max depth (worst-case O(V)).

Edge cases:- src not in graph: returns {src} (or you can choose to return empty set if preferred).- Large/deep graphs may cause RecursionError; consider iterative DFS or increasing recursion limit for production.

EasyTechnical

21 practiced

Define precisely: leaf node, tree height, and node depth. Provide small examples (balanced binary tree and a skewed tree), compute number of nodes as a function of height in each case, and explain the implications for recursion depth and stack usage in tree algorithms.

EasyTechnical

33 practiced

Implement a function search_bst(root, target) in Python that searches for target in a binary search tree and returns the node (or None). Assume TreeNode(val, left, right). Aim for O(h) average-case time and O(1) extra space. Explain how behavior changes for skewed trees and for balanced trees.

Sample Answer

Approach: Use iterative BST search to achieve O(h) time and O(1) extra space (no recursion). Walk down the tree comparing target to node.val and move left or right accordingly; return the node if found, else None.

python

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

def search_bst(root: TreeNode, target: int) -> TreeNode:
    """
    Iterative BST search. Average O(h) time, O(1) extra space.
    """
    node = root
    while node:
        if node.val == target:
            return node
        elif target < node.val:
            node = node.left
        else:
            node = node.right
    return None

Key points:- Uses iteration to avoid call-stack space.- Average-case time O(h) where h is tree height.

Behavior differences:- Skewed tree (like a linked list): h = n, so time becomes O(n).- Balanced tree (e.g., AVL/Red-Black): h = O(log n), so time is O(log n).

Edge cases:- Empty tree (root is None) returns None.- Duplicate values: this returns the first encountered matching node along the search path (BST convention matters).

HardTechnical

26 practiced

Write a Python function is_isomorphic(t1, t2) that checks whether two binary trees are isomorphic in structure (ignoring node values). Then implement is_mirror_isomorphic(t1, t2) that checks whether t2 is the mirror image of t1. Analyze time and space complexity and discuss edge cases.

Sample Answer

To check structural isomorphism we recursively compare presence/absence of children (ignore values). For mirror-isomorphism we check left of one with right of the other and vice versa.

python

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

def is_isomorphic(t1, t2):
    """
    True if t1 and t2 have identical structure (node positions),
    ignoring node values.
    """
    if t1 is None and t2 is None:
        return True
    if (t1 is None) != (t2 is None):
        return False
    # both non-None: structure must match on both children
    return is_isomorphic(t1.left, t2.left) and is_isomorphic(t1.right, t2.right)

def is_mirror_isomorphic(t1, t2):
    """
    True if t2 is the mirror image of t1 structurally.
    """
    if t1 is None and t2 is None:
        return True
    if (t1 is None) != (t2 is None):
        return False
    # compare left of t1 with right of t2 and right of t1 with left of t2
    return is_mirror_isomorphic(t1.left, t2.right) and is_mirror_isomorphic(t1.right, t2.left)

Key points:- Both functions are simple, purely structural checks using recursion.- Time complexity: O(n) where n is number of nodes in the smaller tree being traversed; each node pair visited once.- Space complexity: O(h) recursion stack, where h is tree height (O(n) worst-case skewed, O(log n) balanced).Edge cases:- One or both trees empty.- Different shapes, e.g., same node counts but different arrangement.- Deep trees causing recursion depth limits — consider iterative stack-based traversal for very deep trees. Alternative: BFS comparing null/non-null child positions.

Unlock Full Question Bank

Get access to hundreds of Trees & Graphs Basics interview questions and detailed answers.

Join thousands of developers preparing for their dream job.