Data Structures Using Java
Interview Questions with Answers

41. What is the difference between Binary Tree and Binary Search Tree (BST)?

TreeNode Class (For some of the below examples)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

42. Write a Java method for Inorder Traversal (Recursive and Iterative)

Recursive Inorder Traversal

void inorderRecursive(TreeNode root) {
    if (root == null) return;
    inorderRecursive(root.left);
    System.out.print(root.val + " ");
    inorderRecursive(root.right);
}

Iterative Inorder Traversal

void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        System.out.print(current.val + " ");
        current = current.right;
    }
}

43. Check if a Binary Tree is Balanced

A tree is height-balanced if for every node, height(left) - height(right) ≤ 1
boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}
int checkHeight(TreeNode node) {
    if (node == null) return 0;
    int left = checkHeight(node.left);
    int right = checkHeight(node.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

44. Find the Lowest Common Ancestor (LCA) of Two Nodes in a Binary Tree

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;
}

45. Convert a Binary Tree to Its Mirror Tree

TreeNode mirror(TreeNode node) {
    if (node == null) return null;
    TreeNode left = mirror(node.left);
    TreeNode right = mirror(node.right);
    node.left = right;
    node.right = left;
    return node;
}

46. Check if a Tree is a Subtree of Another

boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    if (isSameTree(s, t)) return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
}
boolean isSameTree(TreeNode s, TreeNode t) {
    if (s == null && t == null) return true;
    if (s == null || t == null || s.val != t.val) return false;
    return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}

47. Implement Level Order Traversal Using a Queue

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

48. Serialize and Deserialize a Binary Tree

Serialization: Convert tree to string (Preorder)

Deserialization: Rebuild tree from string

class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "X";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return buildTree(nodes);
    }
    private TreeNode buildTree(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("X")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

49. Convert a BST to a Doubly Linked List (Inorder-Based)

TreeNode prev = null, head = null;
public TreeNode bstToDLL(TreeNode root) {
    if (root == null) return null;
    convert(root);
    return head;
}
private void convert(TreeNode node) {
    if (node == null) return;
    convert(node.left);
    if (prev == null) head = node;
    else {
        prev.right = node;
        node.left = prev;
    }
    prev = node;
    convert(node.right);
}

50. Count the Number of Leaf Nodes in a Tree

int countLeafNodes(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    return countLeafNodes(root.left) + countLeafNodes(root.right);
}

51. Implement BFS and DFS for a Graph

// Graph: Adjacency List Representation
Map<Integer, List<Integer>> graph = new HashMap<>();
// BFS
void bfs(int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (!visited.contains(node)) {
            visited.add(node);
            System.out.print(node + " ");
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                queue.add(neighbor);
            }
        }
    }
}
// DFS
void dfs(int node, Set<Integer> visited) {
    visited.add(node);
    System.out.print(node + " ");
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) dfs(neighbor, visited);
    }
}

52. Detect a Cycle in a Directed Graph Using DFS

boolean hasCycle(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    Set<Integer> recursionStack = new HashSet<>();
    for (int node : graph.keySet()) {
        if (dfsCycle(node, visited, recursionStack, graph)) return true;
    }
    return false;
}
boolean dfsCycle(int node, Set<Integer> visited, Set<Integer> stack, Map<Integer, List<Integer>> graph) {
    if (stack.contains(node)) return true;
    if (visited.contains(node)) return false;
    visited.add(node);
    stack.add(node);
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (dfsCycle(neighbor, visited, stack, graph)) return true;
    }
    stack.remove(node);
    return false;
}

53. What is a Priority Queue and How is it Implemented Using Heaps in Java?

PriorityQueue is a special queue where elements are dequeued based on priority (not insertion order).

Internally:

• Uses binary heap (min-heap by default)
• Time complexities:
  • add() – O(log n)
  • poll() – O(log n)
  • peek() – O(1)

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(10); pq.offer(5); pq.offer(8);

System.out.println(pq.poll()); // Output: 5 (smallest)

Use custom comparator for max-heap:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

54. Find the Shortest Path in an Unweighted Graph Using BFS

int shortestPath(Map<Integer, List<Integer>> graph, int src, int dest) {
    Queue<Integer> queue = new LinkedList<>();
    Map<Integer, Integer> distance = new HashMap<>();
    queue.offer(src);
    distance.put(src, 0);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == dest) return distance.get(node);
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!distance.containsKey(neighbor)) {
                distance.put(neighbor, distance.get(node) + 1);
                queue.offer(neighbor);
            }
        }
    }
    return -1; // unreachable
}

55. Explain Topological Sorting and Implement It

Topological Sort: Linear ordering of DAG nodes such that for every directed edge u → v, u comes before v.

Use Case: Task scheduling, build systems.

List<Integer> topologicalSort(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    for (int node : graph.keySet()) {
        if (!visited.contains(node)) topoDfs(node, visited, stack, graph);
    }
    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) result.add(stack.pop());
    return result;
}
void topoDfs(int node, Set<Integer> visited, Stack<Integer> stack, Map<Integer, List<Integer>> graph) {
    visited.add(node);
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) topoDfs(neighbor, visited, stack, graph);
    }
    stack.push(node);
}

56. What are Union-Find Data Structures and Their Applications?

Union-Find (Disjoint Set): Efficient structure to manage partitioned sets.

Operations:

• find(x): Find root of set containing x
• union(x, y): Merge sets containing x and y

Optimizations:

• Path Compression (flatten tree)
• Union by Rank (attach smaller to larger)

Applications:

• Kruskal’s Algorithm (MST)
• Cycle detection
• Connected components
• Network connectivity

57. Implement Dijkstra’s Algorithm Using Java and PriorityQueue

class Node implements Comparable<Node> {
    int vertex, weight;
    Node(int v, int w) { vertex = v; weight = w; }
    public int compareTo(Node other) { return this.weight - other.weight; }
}
int[] dijkstra(Map<Integer, List<Node>> graph, int start, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0));
    while (!pq.isEmpty()) {
        Node current = pq.poll();
        for (Node neighbor : graph.getOrDefault(current.vertex, new ArrayList<>())) {
            int newDist = dist[current.vertex] + neighbor.weight;
            if (newDist < dist[neighbor.vertex]) {
                dist[neighbor.vertex] = newDist;
                pq.offer(new Node(neighbor.vertex, newDist));
            }
        }
    }
    return dist;
}

58. Explain Trie Data Structure and Use-Case for Auto-Complete

Trie (Prefix Tree):

• Tree-like structure for efficient prefix matching.
• Each node represents a character, paths form words.

Use Cases:

• Auto-complete
• Spell checker
• Prefix queries
• IP routing (binary trie)

Basic Trie Implementation:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}
class Trie {
    TrieNode root = new TrieNode();
    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray())
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        node.isEndOfWord = true;
    }
    boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) return false;
            node = node.children.get(c);
        }
        return node.isEndOfWord;
    }
}

59. How Would You Implement a Disjoint Set in Java?

class DisjointSet {
    int[] parent, rank;
    DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // Path Compression
        return parent[x];
    }
    void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

60. What is a Segment Tree and When Should It Be Used?

Segment Tree: A binary tree to solve range queries (sum, min, max) in O(log n) time.

Use Cases:

• Range sum / min / max
• Range updates
• Competitive programming
• Sliding window problems

Operations:

• Build: O(n)
• Query: O(log n)
• Update: O(log n)

Basic Segment Tree for Range Sum:

class SegmentTree {
    int[] tree, arr;
    int n;
    SegmentTree(int[] input) {
        arr = input;
        n = input.length;
        tree = new int[4 * n];
        build(0, 0, n - 1);
    }
    void build(int node, int start, int end) {
        if (start == end) tree[node] = arr[start];
        else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
    int query(int l, int r) { return query(0, 0, n - 1, l, r); }
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;         // No overlap
        if (l <= start && end <= r) return tree[node]; // Total overlap
        int mid = (start + end) / 2;
        return query(2 * node + 1, start, mid, l, r) +
               query(2 * node + 2, mid + 1, end, l, r);
    }
}