Tree & Graph Problems

Posted on: February 1, 2025 Posted by: rahulgite Comments: 0

Problem 1: Maximum Depth of Binary Tree

Explanation:

Given a binary tree, return its maximum depth.

Approach:

  1. Recursive DFS (Depth-First Search):
    • If the node is null, return 0.
    • Recursively compute the depth of the left and right subtrees.
    • Return 1 + max(leftDepth, rightDepth).
  2. Iterative BFS (Breadth-First Search) Alternative:
    • Use a queue to traverse level by level.
    • Count the number of levels.

Time & Space Complexity:

  • Time Complexity: O(n), since we visit each node once.
  • Space Complexity: O(h), where h is the height of the tree (O(log n) for balanced trees, O(n) for skewed trees).

Java Implementation:

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

public class MaxDepthBinaryTree {
    /**
     * Computes the maximum depth of a binary tree.
     * @param root - root node of the tree
     * @return maximum depth of the tree
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        
        System.out.println("Output: " + maxDepth(root));
    }
}

Example:

Input:

    3
   / \
  9  20
    /  \
   15   7

Output:

3

Edge Cases Considered:

  • Empty tree → Should return 0.
  • Single node tree → Should return 1.
  • Skewed tree (linked list-like structure) → Should return n.

Problem 2: Validate Binary Search Tree

Explanation:

Given a binary tree, determine if it is a valid Binary Search Tree (BST).

Approach:

  1. Recursive Inorder Traversal:
    • Ensure left < root < right at all nodes.
    • Use a helper function with min/max constraints.
  2. Iterative Inorder Traversal Alternative:
    • Use a stack and keep track of the last visited node.

Time & Space Complexity:

  • Time Complexity: O(n), since each node is visited once.
  • Space Complexity: O(h), where h is the height of the tree.

Java Implementation:

public class ValidateBST {
    /**
     * Validates if a binary tree is a BST.
     * @param root - root node of the tree
     * @return true if it is a BST, false otherwise
     */
    public static boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private static boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        
        System.out.println("Output: " + isValidBST(root));
    }
}

Example:

Input:

    2
   / \
  1   3

Output:

true

Edge Cases Considered:

  • Empty tree → Should return true.
  • Single node tree → Should return true.
  • Tree with incorrect BST structure → Should return false.

Problem 3: Count Complete Tree Nodes

Explanation:

Given a complete binary tree, return the number of nodes in the tree.

Approach:

  1. Binary Search Approach:
    • Compute the tree height.
    • Use binary search to determine the number of nodes in the last level.
  2. Recursive DFS Alternative:
    • If leftHeight == rightHeight, the left subtree is full.
    • Otherwise, recurse on both subtrees.

Time & Space Complexity:

  • Time Complexity: O(log^2 n), since we traverse the height O(log n) times.
  • Space Complexity: O(log n), due to recursive stack calls.

Java Implementation:

public class CountCompleteTreeNodes {
    /**
     * Counts the number of nodes in a complete binary tree.
     * @param root - root node of the tree
     * @return total number of nodes
     */
    public static int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            return (1 << rightHeight) + countNodes(root.left);
        }
    }
    
    private static int getHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.left;
        }
        return height;
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        
        System.out.println("Output: " + countNodes(root));
    }
}

Example:

Input:

    1
   / \
  2   3
 / \  /
4   5 6

Output:

6

Edge Cases Considered:

  • Empty tree → Should return 0.
  • Single node tree → Should return 1.
  • Full tree vs incomplete tree → Should count correctly in both cases.

Problem 4: Unique Binary Search Trees II

Explanation:

Given an integer n, return all structurally unique BSTs (binary search trees) that store values 1...n.

Approach:

  1. Recursive Backtracking:
    • Generate all possible BSTs for each i as the root.
    • Recursively compute left and right subtrees.
  2. Use a Memoization Table: Store previously computed values to avoid redundant calculations.

Time & Space Complexity:

  • Time Complexity: O(4^n / sqrt(n)), based on the Catalan number.
  • Space Complexity: O(4^n / sqrt(n)), for storing all possible trees.

Java Implementation:

import java.util.*;

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

public class UniqueBSTII {
    /**
     * Generates all unique BSTs for values 1 to n.
     * @param n - number of nodes
     * @return list of unique BST root nodes
     */
    public static List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTreesHelper(1, n);
    }
    
    private static List<TreeNode> generateTreesHelper(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = generateTreesHelper(start, i - 1);
            List<TreeNode> rightTrees = generateTreesHelper(i + 1, end);
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("Generated BSTs for n = 3: " + generateTrees(3).size());
    }
}

Example:

Input:

n = 3

Output:

5

Edge Cases Considered:

  • n = 0 → Should return an empty list.
  • n = 1 → Should return a single node tree.
  • Larger n values → Should correctly generate all unique BSTs.

Problem 5: All Paths From Source to Target

Explanation:

Given a directed, acyclic graph (DAG) with n nodes, find all paths from node 0 to node n-1.

Approach:

  1. DFS with Backtracking:
    • Start from node 0 and recursively explore all paths to n-1.
    • Store the current path and backtrack when done.

Time & Space Complexity:

  • Time Complexity: O(2^n * n), as we explore all paths.
  • Space Complexity: O(2^n * n), to store all paths.

Java Implementation:

import java.util.*;

public class AllPathsSourceTarget {
    /**
     * Finds all paths from node 0 to node n-1 in a DAG.
     * @param graph - adjacency list of the graph
     * @return list of all possible paths
     */
    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(graph, 0, path, result);
        return result;
    }
    
    private static void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> result) {
        if (node == graph.length - 1) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int next : graph[node]) {
            path.add(next);
            dfs(graph, next, path, result);
            path.remove(path.size() - 1);
        }
    }
    
    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {3}, {3}, {}};
        System.out.println("Output: " + allPathsSourceTarget(graph));
    }
}

Example:

Input:

graph = [[1,2],[3],[3],[]]

Output:

[[0,1,3],[0,2,3]]

Edge Cases Considered:

  • Single-node graph → Should return [[0]].
  • No path from 0 to n-1 → Should return an empty list.
  • Graph with multiple branches → Should correctly list all valid paths.

Problem 6: Binary Tree Zigzag Level Order Traversal

Explanation:

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values.

Approach:

  1. Use BFS (Breadth-First Search) with a Queue:
    • Traverse level by level.
    • Reverse the order for every alternate level.

Time & Space Complexity:

  • Time Complexity: O(n), since we visit each node once.
  • Space Complexity: O(n), for storing results and queue.

Java Implementation:

import java.util.*;

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

public class ZigzagLevelOrder {
    /**
     * Returns zigzag level order traversal of a binary tree.
     * @param root - root node of the tree
     * @return list of levels in zigzag order
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val);
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        
        System.out.println("Output: " + zigzagLevelOrder(root));
    }
}

Example:

Input:

    3
   / \
  9  20
    /  \
   15   7

Output:

[[3], [20, 9], [15, 7]]

Edge Cases Considered:

  • Empty tree → Should return [].
  • Single-node tree → Should return [[root]].
  • Multiple levels with varying structures → Should correctly alternate levels.

Problem 7: Serialize and Deserialize Binary Tree

Explanation:

Serialize a binary tree to a string and deserialize it back to a tree structure.

Approach:

  1. Use BFS for Serialization:
    • Convert tree nodes into a string using level order traversal.
    • Use "null" for missing nodes.
  2. Use BFS for Deserialization:
    • Split the string and reconstruct the tree using a queue.

Time & Space Complexity:

  • Time Complexity: O(n), as we visit each node once.
  • Space Complexity: O(n), for storing serialized data and queue.

Java Implementation:

import java.util.*;

public class SerializeDeserializeTree {
    /**
     * Encodes a tree to a single string.
     * @param root - root node of the tree
     * @return serialized string representation
     */
    public static String serialize(TreeNode root) {
        if (root == null) return "null";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        StringBuilder sb = new StringBuilder();
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("null,");
            } else {
                sb.append(node.val).append(",");
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return sb.toString();
    }
    
    /**
     * Decodes the serialized string back into a binary tree.
     * @param data - serialized tree string
     * @return root of the deserialized tree
     */
    public static TreeNode deserialize(String data) {
        if (data.equals("null")) return null;
        String[] nodes = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        for (int i = 1; i < nodes.length; i++) {
            TreeNode parent = queue.poll();
            if (!nodes[i].equals("null")) {
                parent.left = new TreeNode(Integer.parseInt(nodes[i]));
                queue.add(parent.left);
            }
            if (++i < nodes.length && !nodes[i].equals("null")) {
                parent.right = new TreeNode(Integer.parseInt(nodes[i]));
                queue.add(parent.right);
            }
        }
        return root;
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        
        String serialized = serialize(root);
        System.out.println("Serialized: " + serialized);
        TreeNode deserialized = deserialize(serialized);
        System.out.println("Deserialized Root: " + deserialized.val);
    }
}

Example:

Input:

    1
   / \
  2   3
     / \
    4   5

Output:

Serialized: "1,2,3,null,null,4,5,null,null,null,null,"
Deserialized Root: 1

Edge Cases Considered:

  • Empty tree → Should return "null".
  • Single-node tree → Should serialize and deserialize correctly.
  • Complex tree structures → Should maintain correct relationships.

Problem 8: Path Sum

Explanation:

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all values along the path equals targetSum.

Approach:

  1. Recursive DFS:
    • Subtract the current node’s value from targetSum.
    • If a leaf node is reached, check if targetSum == 0.
    • Recursively check left and right subtrees.

Time & Space Complexity:

  • Time Complexity: O(n), since we visit every node once.
  • Space Complexity: O(h), where h is the tree height (O(log n) for balanced trees, O(n) for skewed trees).

Java Implementation:

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

public class PathSum {
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.right.right = new TreeNode(1);
        
        System.out.println("Output: " + hasPathSum(root, 22));
    }
}

Example:

Input:

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output:

true

Edge Cases Considered:

  • Empty tree → Should return false.
  • Single-node tree with matching target → Should return true.
  • Multiple valid paths → Should correctly detect any valid path.

Problem 9: Verify Preorder Serialization of a Binary Tree

Explanation:

Given a string preorder, verify whether it is a valid preorder serialization of a binary tree.

Approach:

  1. Stack Simulation:
    • Track the number of available slots for nodes.
    • Process each node and adjust slots accordingly.
    • Ensure the tree structure remains valid throughout.

Time & Space Complexity:

  • Time Complexity: O(n), since we process each node once.
  • Space Complexity: O(n), for storing stack elements.

Java Implementation:

public class VerifyPreorderSerialization {
    public static boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int slots = 1;
        for (String node : nodes) {
            if (--slots < 0) return false;
            if (!node.equals("#")) slots += 2;
        }
        return slots == 0;
    }
    
    public static void main(String[] args) {
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        System.out.println("Output: " + isValidSerialization(preorder));
    }
}

Example:

Input:

preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"

Output:

true

Edge Cases Considered:

  • Only null nodes → Should validate correctly.
  • Extra nodes remaining at the end → Should return false.
  • Unbalanced tree → Should correctly detect invalid cases.

Problem 10: Binary Tree Level Order Traversal

Explanation:

Given the root of a binary tree, return its level order traversal as a list of lists.

Approach:

  1. BFS with Queue:
    • Use a queue to process nodes level by level.
    • Track levels separately and store them in lists.

Time & Space Complexity:

  • Time Complexity: O(n), since we visit every node once.
  • Space Complexity: O(n), for storing queue elements.

Java Implementation:

import java.util.*;

public class BinaryTreeLevelOrderTraversal {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        
        System.out.println("Output: " + levelOrder(root));
    }
}

Example:

Input:

root = [3,9,20,null,null,15,7]

Output:

[[3], [9,20], [15,7]]

Edge Cases Considered:

  • Empty tree → Should return an empty list.
  • Single-node tree → Should return a single-level list.
  • Unbalanced tree → Should correctly traverse level-wise.

Problem 11: Alien Dictionary

Explanation:

Given a list of words sorted lexicographically according to an unknown alphabet, derive the order of letters.

Approach:

  1. Topological Sort:
    • Build a graph where edges represent letter precedence.
    • Perform Kahn’s Algorithm (BFS) to derive the order.

Time & Space Complexity:

  • Time Complexity: O(n * k), where n is the number of words and k is the average word length.
  • Space Complexity: O(n * k), for storing the graph.

Java Implementation:

import java.util.*;

public class AlienDictionary {
    public static String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new HashSet<>());
                inDegree.putIfAbsent(c, 0);
            }
        }
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (!graph.get(w1.charAt(j)).contains(w2.charAt(j))) {
                        graph.get(w1.charAt(j)).add(w2.charAt(j));
                        inDegree.put(w2.charAt(j), inDegree.get(w2.charAt(j)) + 1);
                    }
                    break;
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (char c : inDegree.keySet()) {
            if (inDegree.get(c) == 0) queue.offer(c);
        }
        StringBuilder order = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char neighbor : graph.get(c)) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) queue.offer(neighbor);
            }
        }
        return order.length() == inDegree.size() ? order.toString() : "";
    }
    
    public static void main(String[] args) {
        String[] words = {"wrt", "wrf", "er", "ett", "rftt"};
        System.out.println("Output: " + alienOrder(words));
    }
}

Example:

Input:

words = ["wrt", "wrf", "er", "ett", "rftt"]

Output:

"wertf"

Edge Cases Considered:

  • Single-word list → Should return all characters in order.
  • Conflicting orders → Should return empty string.
  • Longer prefix followed by shorter word → Should return empty string.

Problem 12: House Robber III

Explanation:

A thief can rob houses in a binary tree but cannot rob two directly-linked houses. Find the maximum amount that can be robbed.

Approach:

  1. Dynamic Programming on Trees:
    • Use a postorder traversal to compute max robbed amounts.
    • Maintain two values per node: robbed and not robbed.

Time & Space Complexity:

  • Time Complexity: O(n), since we visit each node once.
  • Space Complexity: O(h), where h is the tree height.

Java Implementation:

public class HouseRobberIII {
    public static int rob(TreeNode root) {
        int[] result = robHelper(root);
        return Math.max(result[0], result[1]);
    }
    
    private static int[] robHelper(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = robHelper(node.left);
        int[] right = robHelper(node.right);
        int rob = node.val + left[1] + right[1];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, notRob};
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        
        System.out.println("Output: " + rob(root));
    }
}

Example:

Input:

root = [3,2,3,null,3,null,1]

Output:

7

Edge Cases Considered:

  • Empty tree → Should return 0.
  • Single-node tree → Should return node value.
  • Tree with alternating large and small values → Should still compute correctly.

Leave a Comment