Cheatsheet for graph Problems in the coding interviews

Graph Problems and Graph Terminology are important to understand the syllabus of FAANG Interviews preparation.

What is important and what should be cover before jumping over problem, is important.

Since, if we skip a topic to understand the graph theory then you will always skip to solve the problem and so we should not skip any graph theory topics.

So, Let's see the common graph problems that we will discuss in future articles.

The common graph problems are categorized as below:

1. Traversal Problems

Traversal problems in graph includes navigating all the nodes of a graph (or visiting the all vertices of a graph).

Graph Traversal is similar in concept to a tree traversal.

The tree traversals visit every node exactly once in preorder, inorder, or postorder.

There are many tree traversals algorithms exist because many problems need the nodes to be visited in a particular order.

Similarly Graph Traversal algorithms starts from a starting vertex and try to visit the remaining vertices from there.

We can find many possible trouble cases:-

There may be possibility that we are unable to reach all the vertices from a starting vertex.

This occurs when the graph is not connected.

Another problem can found like the graph might contain cycles

We must make sure that this cycle should not cause the traversal algorithm to go into infinite loop.

So, there are two main traversal algorithms:-

• 1. Breadth-First Search (BFS):

  • Find the shortest path in an unweighted graph.

  • Level-order traversal in trees.

• 2. Depth-First Search (DFS):

  • Find connected components in a graph.

  • Detect cycles in a graph.

  • Topological sorting of a Directed Acyclic Graph (DAG).

2. Shortest Path Problems

• Dijkstra's Algorithm:

  • Find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.

• Bellman-Ford Algorithm:

  • Find the shortest path from a source vertex to all other vertices in a graph that may have negative weights.

• Floyd-Warshall Algorithm:

  • Find shortest paths between all pairs of vertices in a weighted graph.

• A* Algorithm:

  • Find the shortest path in a weighted graph using heuristics (used in pathfinding algorithms).

Please checkout our best article on Shortest path in a graph.

Shortest path in a graph

3. Minimum Spanning Tree (MST) Problems

• Kruskal’s Algorithm:

  • Find the Minimum Spanning Tree (MST) of a graph using a union-find data structure.

• Prim’s Algorithm:

  • Find the MST by growing the tree from an initial vertex using a priority queue.

4. Cycle Detection Problems

• Cycle Detection in Directed Graphs:

  • Use DFS to detect cycles in a directed graph (e.g., to check if a graph is a DAG).

• Cycle Detection in Undirected Graphs:

  • Use union-find data structure to detect cycles in an undirected graph.

5. Connectivity Problems

• Connected Components:

  • Find all connected components in an undirected graph.

• Articulation Points:

  • Find vertices whose removal increases the number of connected components.

• Bridges:

  • Find edges whose removal increases the number of connected components.

6. Topological Sorting

• Topological Sorting:

  • Order vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before v.

7. Graph Coloring

• Graph Coloring:

  • Assign colors to vertices of a graph such that no two adjacent vertices share the same color (used in scheduling problems).

• Chromatic Number:

  • Determine the minimum number of colors needed to color a graph.

8. Flow Problems

• Maximum Flow:

  • Find the maximum flow from a source to a sink in a flow network (using algorithms like Ford-Fulkerson, Edmonds-Karp).

• Minimum Cut:

  • Find the smallest cut (set of edges) that separates the source and sink in a flow network.

9. Matching Problems

• Maximum Bipartite Matching:

  • Find the maximum matching in a bipartite graph (e.g., job assignment problems).

• Hungarian Algorithm:

  • Solve the assignment problem where each task is assigned to exactly one worker to minimize cost.

10. Distance Problems

• Diameter of a Graph:

  • Find the longest shortest path between any pair of vertices in a graph.

• K-Shortest Paths:

  • Find multiple shortest paths between two vertices in a weighted graph.

These problems cover a broad spectrum of graph theory and are commonly encountered in various domains, including computer science, operations research, and optimization.

Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal. The traversal organizes nodes by their vertical positions. Nodes in the same column and row are sorted by value.

Approach

We utilize a combination of Breadth-First Search (BFS) and a nested data structure (TreeMap) to store nodes by their coordinates efficiently. The steps are:

• Traverse the tree using BFS while keeping track of each node's row and column.
• Store nodes in a nested TreeMap, ensuring columns and rows are sorted.
• Sort nodes in the same position by their values and build the result.

Code Implementation

class Tuple {
    TreeNode node;
    int row, col;

    public Tuple(TreeNode node, int row, int col) {
        this.node = node;
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public List> verticalTraversal(TreeNode root) {
        TreeMap>> map = new TreeMap<>();
        Queue queue = new LinkedList<>();
        queue.offer(new Tuple(root, 0, 0));

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            TreeNode node = t.node;
            int row = t.row, col = t.col;

            map.putIfAbsent(col, new TreeMap<>());
            map.get(col).putIfAbsent(row, new PriorityQueue<>());
            map.get(col).get(row).offer(node.val);

            if (node.left != null) queue.offer(new Tuple(node.left, row + 1, col - 1));
            if (node.right != null) queue.offer(new Tuple(node.right, row + 1, col + 1));
        }

        List> result = new ArrayList<>();
        for (TreeMap> rows : map.values()) {
            List column = new ArrayList<>();
            for (PriorityQueue nodes : rows.values()) {
                while (!nodes.isEmpty()) column.add(nodes.poll());
            }
            result.add(column);
        }

        return result;
    }
}
        

Complexity Analysis

Time Complexity: O(n log n), where n is the number of nodes (due to sorting).
Space Complexity: O(n), for storing the tree structure in the map.

Vertical Order Traversal of a Binary Tree

The problem of Vertical Order Traversal of a Binary Tree combines the concepts of binary tree traversal and coordinate-based sorting. It is widely used in various tree visualization and transformation algorithms.

Problem Statement

Given the root of a binary tree, the goal is to return the vertical order traversal of its nodes' values. In this traversal, nodes are grouped by their vertical columns, sorted by their row positions, and further sorted by values when ties occur.

Specifically:

• Each node in the binary tree is assigned a coordinate: (row, column).
• The left child of a node at (row, col) is located at (row + 1, col - 1).
• The right child is located at (row + 1, col + 1).
• The vertical order of traversal groups nodes with the same column index, sorted by row and value.

Approach to Solve the Problem

To efficiently implement vertical order traversal, we can use one of the following approaches:

1. Breadth-First Search (BFS)

This method uses a queue to perform a level-order traversal while keeping track of the coordinates of each node.

1. Start with the root node at (0, 0) and enqueue it.
2. Dequeue nodes one by one, storing their values along with their coordinates in a map.
3. Group nodes by column index and sort them by row and value.

2. Depth-First Search (DFS)

In the DFS approach, we recursively traverse the tree while passing the current coordinates as parameters.

• For each node, record its value and coordinates in a map.
• Visit the left and right children with updated coordinates.
• Finally, sort the map by column, row, and value.

3. Optimized Coordinate Tracking

Using advanced data structures such as a sorted map or a min-heap allows for efficient grouping and sorting of nodes during traversal.

Implementation

Here is a Python implementation of the BFS-based approach:

from collections import defaultdict, deque

def verticalTraversal(root):
    # Map to store nodes grouped by column
    column_map = defaultdict(list)
    # Queue to perform BFS, storing nodes and their coordinates
    queue = deque([(root, 0, 0)])  # (node, row, column)
    
    while queue:
        node, row, col = queue.popleft()
        if node:
            column_map[col].append((row, node.val))
            queue.append((node.left, row + 1, col - 1))
            queue.append((node.right, row + 1, col + 1))
    
    # Sort columns and their values
    sorted_columns = sorted(column_map.keys())
    result = []
    for col in sorted_columns:
        column_nodes = sorted(column_map[col], key=lambda x: (x[0], x[1]))
        result.append([val for _, val in column_nodes])
    return result
        

Here is the Java implementation using DFS:

import java.util.*;

class Solution {
    Map> columnMap = new TreeMap<>();
    
    public List> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        List> result = new ArrayList<>();
        
        for (List values : columnMap.values()) {
            values.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
            List sortedColumn = new ArrayList<>();
            for (int[] value : values) {
                sortedColumn.add(value[1]);
            }
            result.add(sortedColumn);
        }
        
        return result;
    }
    
    private void dfs(TreeNode node, int row, int col) {
        if (node == null) return;
        columnMap.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
        dfs(node.left, row + 1, col - 1);
        dfs(node.right, row + 1, col + 1);
    }
}
        

Example

Consider the binary tree:

            Tree Structure:
                3
               / \
              9   20
                  /  \
                 15   7
        

The vertical order traversal for this tree is:

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

Complexity Analysis

Time Complexity: O(n log n), where n is the number of nodes. Sorting the nodes by column adds logarithmic overhead.

Space Complexity: O(n), due to the storage required for the map and the recursion stack (in the case of DFS).

Applications

• Tree visualization and rendering in GUIs.
• Problems that require coordinate-based traversal of data structures.
• Analyzing spatial relationships in hierarchical data.

Conclusion

Vertical Order Traversal of a Binary Tree is a versatile problem that demonstrates the integration of traversal techniques and sorting. It is an excellent exercise for mastering tree algorithms and understanding spatial relationships in hierarchical data structures.

Explore variations of this problem by incorporating additional constraints, such as custom sorting orders or multi-branch trees, to deepen your understanding.

Vertical Order Traversal of a Binary Tree is a significant problem that highlights tree traversal techniques combined with coordinate-based sorting. It requires organizing nodes column-wise and sorting them based on their positions.

Problem Statement:
Given the root of a binary tree, perform a vertical order traversal. Each node's position is determined by its depth (row) and horizontal alignment (column). The rules for positioning are as follows:

• The left child of a node at (row, col) is positioned at (row + 1, col - 1).
• The right child of a node at (row, col) is positioned at (row + 1, col + 1).

Further details and explanation continue here... Let me know if you'd like me to elaborate!

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree. The cloned tree is a copy of the original tree. Return a reference to the same node in the cloned tree. Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Approach 1: DFS: Recursive Inorder Traversal.

class Solution {
    TreeNode ans, target;
    
    public void inorder(TreeNode o, TreeNode c) {
        if (o != null) {
            inorder(o.left, c.left);
            if (o == target) {
                ans = c;    
            }
            inorder(o.right, c.right);    
        }
    }
    
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        this.target = target;
        inorder(original, cloned);
        return ans;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

This problem is an interesting application of tree traversal techniques and highlights the relationship between a binary tree and its exact clone.

Problem Statement

You are given the root of a binary tree and a node within the tree called target. You are also given a cloned version of this binary tree. The task is to locate and return the corresponding node in the cloned tree that matches the target node in the original tree.

Key Points to Note:

• The cloned binary tree is an exact copy of the original tree, including structure and node values.
• We are guaranteed that the target node exists in the original binary tree.
• The target node is identified by reference, not just by value.

Approach to Solve the Problem

To solve this problem, we can use one of the following approaches:

1. Recursive Traversal

Using recursion, we traverse both the original tree and the cloned tree simultaneously. At each step:

1. If the current node in the original tree matches the target node, return the corresponding node in the cloned tree.
2. Otherwise, recursively search the left and right subtrees.

2. Iterative Traversal

We can also solve this problem iteratively using a queue. The algorithm involves:

• Using two queues to perform a level-order traversal (BFS) on both trees simultaneously.
• At each step, compare the node from the original tree with the target node.
• If they match, return the corresponding node from the cloned tree.

3. Leveraging Tree Properties

Since the trees are identical in structure, we can use the symmetry of the cloned tree to locate the corresponding node directly during traversal. This avoids additional checks and comparisons.

Implementation

Here is the Java implementation for the recursive approach:

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        // Base case: if the original node is null, return null
        if (original == null) {
            return null;
        }
        // If the current original node is the target, return the cloned node
        if (original == target) {
            return cloned;
        }
        // Recursively search in the left subtree
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if (left != null) {
            return left;
        }
        // Recursively search in the right subtree
        return getTargetCopy(original.right, cloned.right, target);
    }
}
        

And here is the BFS-based iterative implementation:

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Queue queueOriginal = new LinkedList<>();
        Queue queueCloned = new LinkedList<>();
        queueOriginal.offer(original);
        queueCloned.offer(cloned);

        while (!queueOriginal.isEmpty()) {
            TreeNode currentOriginal = queueOriginal.poll();
            TreeNode currentCloned = queueCloned.poll();

            if (currentOriginal == target) {
                return currentCloned;
            }
            if (currentOriginal.left != null) {
                queueOriginal.offer(currentOriginal.left);
                queueCloned.offer(currentCloned.left);
            }
            if (currentOriginal.right != null) {
                queueOriginal.offer(currentOriginal.right);
                queueCloned.offer(currentCloned.right);
            }
        }
        return null;
    }
}
        

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once in both the original and cloned trees.

Space Complexity: O(h), where h is the height of the binary tree. This accounts for the stack space used in the recursive approach or the queue space in the iterative approach.

Example

Consider the following binary tree:

            Original Tree               Cloned Tree
                7                          7
               / \                        / \
              4   3                      4   3
                 / \                        / \
                6   19                     6   19
        

If the target node is 3 in the original tree, the corresponding node in the cloned tree is also 3.

Applications

• Useful in problems involving tree cloning and reference-based node identification.
• Demonstrates traversal techniques applicable to other tree-related problems.

Conclusion

This problem is a great exercise for understanding binary tree traversal and manipulation. The key takeaway is that, regardless of the approach (recursive or iterative), the identical structure of the cloned tree ensures that the corresponding node can always be located efficiently.

Explore this problem further by implementing it in different programming languages or extending it to handle more complex scenarios, such as multi-branch trees or trees with additional metadata.

All Nodes Distance K in Binary Tree

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node. You can return the answer in any order.

Approach 1:

class Solution {
    Map> graph;
    List answer;
    Set visited;

    public List distanceK(TreeNode root, TreeNode target, int k) {
        graph = new HashMap<>();
        buildGraph(root, null);

        answer = new ArrayList<>();
        visited = new HashSet<>();
        visited.add(target.val);

        dfs(target.val, 0, k);

        return answer;
    }

    // Recursively build the undirected graph from the given binary tree.
    private void buildGraph(TreeNode cur, TreeNode parent) {
        if (cur != null && parent != null) {
            graph.computeIfAbsent(cur.val, k -> new ArrayList<>()).add(parent.val);
            graph.computeIfAbsent(parent.val, k -> new ArrayList<>()).add(cur.val);
        }
        if (cur.left != null) {
            buildGraph(cur.left, cur);
        }
        if (cur.right != null) {
            buildGraph(cur.right, cur);
        }
    }

    private void dfs(int cur, int distance, int k) {
        if (distance == k) {
            answer.add(cur);
            return;
        }
        for (int neighbor : graph.getOrDefault(cur, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                dfs(neighbor, distance + 1, k);
            }
        }
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

All Nodes Distance K in Binary Tree

The problem of finding All Nodes Distance K in Binary Tree is a popular tree-based challenge that involves identifying nodes located at a specific distance from a given target node. This problem is widely encountered in technical interviews and emphasizes traversal, graph-like thinking, and distance calculations.

Problem Statement

Given the root of a binary tree, a target node, and an integer K, return all the nodes that are exactly K edges away from the target node.

Rules to consider:

• The binary tree is undirected, meaning edges can be traversed in both directions.
• If there are multiple nodes at the same distance, their order in the output does not matter.
• If no nodes exist at distance K, the output is an empty list.

Approach to Solve the Problem

The problem can be tackled in three main steps:

1. Convert the Tree into a Graph

Since nodes can be traversed in both directions, treat the binary tree as a graph where each node is connected to its parent, left child, and right child. Use an adjacency list to represent this graph.

2. Perform a Breadth-First Search (BFS)

Using the target node as the starting point, perform a level-order traversal (BFS) to identify all nodes at distance K.

3. Handle Edge Cases

Ensure the implementation correctly handles scenarios where:

• The target node is null.
• The binary tree contains only one node.
• No nodes are at distance K.

Implementation

Here is the Python implementation:

from collections import defaultdict, deque

def distanceK(root, target, K):
    # Step 1: Convert Tree into Graph
    def build_graph(node, parent):
        if not node:
            return
        if parent:
            graph[node.val].append(parent.val)
            graph[parent.val].append(node.val)
        build_graph(node.left, node)
        build_graph(node.right, node)
    
    graph = defaultdict(list)
    build_graph(root, None)

    # Step 2: Perform BFS from Target Node
    visited = set()
    queue = deque([(target.val, 0)])  # (node value, current distance)
    result = []

    while queue:
        current, distance = queue.popleft()
        if current in visited:
            continue
        visited.add(current)
        if distance == K:
            result.append(current)
        elif distance < K:
            for neighbor in graph[current]:
                queue.append((neighbor, distance + 1))
    
    return result
        

Here is a Java implementation:

import java.util.*;

class Solution {
    Map> graph = new HashMap<>();
    
    public List distanceK(TreeNode root, TreeNode target, int K) {
        buildGraph(root, null);
        return bfs(target, K);
    }
    
    private void buildGraph(TreeNode node, TreeNode parent) {
        if (node == null) return;
        graph.putIfAbsent(node, new ArrayList<>());
        if (parent != null) {
            graph.get(node).add(parent);
            graph.get(parent).add(node);
        }
        buildGraph(node.left, node);
        buildGraph(node.right, node);
    }
    
    private List bfs(TreeNode target, int K) {
        Queue queue = new LinkedList<>();
        Set visited = new HashSet<>();
        queue.offer(target);
        visited.add(target);
        int distance = 0;
        
        while (!queue.isEmpty()) {
            if (distance == K) {
                List result = new ArrayList<>();
                for (TreeNode node : queue) {
                    result.add(node.val);
                }
                return result;
            }
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                for (TreeNode neighbor : graph.get(current)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            distance++;
        }
        return new ArrayList<>();
    }
}
        

Example

Consider the binary tree:

            Tree Structure:
                3
               / \
              5   1
             / \ / \
            6  2 0  8
               / \
              7   4
        

If the target node is 5 and K = 2, the nodes at distance 2 are:

• [7, 4, 1]

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. The graph construction and BFS traversal each take O(n).

Space Complexity: O(n), due to the adjacency list and BFS queue.

Applications

• Tree-based queries in database systems.
• Network analysis, such as finding devices within a certain hop distance.
• Visualizing relationships in hierarchical data structures.

Conclusion

The problem of finding all nodes at distance K from a target node in a binary tree is an excellent exercise in understanding the interplay between trees and graphs. By converting the tree into a graph and using BFS, we can efficiently solve the problem while gaining deeper insights into traversal and distance calculations.

Try experimenting with different graph representations and traversal techniques to optimize performance and handle edge cases gracefully.

Smallest Subtree with all the Deepest Nodes

Given the root of a binary tree, the depth of each node is the shortest distance to the root. Return the smallest subtree such that it contains all the deepest nodes in the original tree. A node is called the deepest if it has the largest depth possible among any node in the entire tree. The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Approach 1: Paint Deepest Nodes

class Solution {
    Map depth;
    int max_depth;
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        depth = new HashMap();
        depth.put(null, -1);
        dfs(root, null);
        max_depth = -1;
        for (Integer d: depth.values())
            max_depth = Math.max(max_depth, d);

        return answer(root);
    }

    public void dfs(TreeNode node, TreeNode parent) {
        if (node != null) {
            depth.put(node, depth.get(parent) + 1);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }

    public TreeNode answer(TreeNode node) {
        if (node == null || depth.get(node) == max_depth)
            return node;
        TreeNode L = answer(node.left),
                    R = answer(node.right);
        if (L != null && R != null) return node;
        if (L != null) return L;
        if (R != null) return R;
        return null;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

Smallest Subtree with all the Deepest Nodes

The problem Smallest Subtree with all the Deepest Nodes is a fascinating challenge in binary tree analysis. It involves determining the smallest subtree that contains all the deepest nodes in a binary tree. This problem is an excellent test of tree traversal techniques and depth calculation logic.

Problem Statement

Given the root of a binary tree, return the root of the smallest subtree that contains all the deepest nodes. A node is considered "deepest" if it is at the maximum depth of the binary tree.

Key points:

• There may be multiple deepest nodes.
• The smallest subtree is the subtree rooted at the lowest common ancestor of all the deepest nodes.

Approach to Solve the Problem

Solving this problem involves two main steps:

1. Calculate Depths

Perform a depth-first search (DFS) to determine the maximum depth of the tree and identify the deepest nodes.

2. Identify the Smallest Subtree

Use a recursive approach to find the lowest common ancestor (LCA) of all the deepest nodes. This LCA will be the root of the smallest subtree containing all the deepest nodes.

Implementation

Here is the Python implementation:

class Solution:
    def subtreeWithAllDeepest(self, root):
        def dfs(node):
            if not node:
                return (0, None)
            left_depth, left_subtree = dfs(node.left)
            right_depth, right_subtree = dfs(node.right)

            if left_depth > right_depth:
                return (left_depth + 1, left_subtree)
            elif right_depth > left_depth:
                return (right_depth + 1, right_subtree)
            else:
                return (left_depth + 1, node)

        return dfs(root)[1]
        

Here is a Java implementation:

class Solution {
    class Result {
        TreeNode node;
        int depth;
        Result(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
    
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    private Result dfs(TreeNode node) {
        if (node == null) return new Result(null, 0);

        Result left = dfs(node.left);
        Result right = dfs(node.right);

        if (left.depth > right.depth) {
            return new Result(left.node, left.depth + 1);
        } else if (right.depth > left.depth) {
            return new Result(right.node, right.depth + 1);
        } else {
            return new Result(node, left.depth + 1);
        }
    }
}
        

Example

Consider the binary tree:

            Tree Structure:
                3
               / \
              5   1
             / \ / \
            6  2 0  8
               / \
              7   4
        

In this tree:

• The deepest nodes are 7 and 4.
• The smallest subtree containing both is the subtree rooted at 2.

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once during the DFS traversal.

Space Complexity: O(h), where h is the height of the tree. This accounts for the recursive call stack.

Applications

• Identifying critical nodes in hierarchical data structures.
• Optimizing search operations in tree-based systems.
• Useful in graph-related problems where depth plays a key role.

Conclusion

The problem Smallest Subtree with all the Deepest Nodes is a classic tree problem that tests your understanding of depth calculation, recursion, and binary tree traversal. By carefully identifying the depths of nodes and recursively determining the lowest common ancestor, the problem can be solved efficiently.

Practice with variations of the problem to strengthen your grasp on recursion and tree manipulation techniques.

Number of Good Leaf Nodes Pairs

You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance. Return the number of good leaf node pairs in the tree.

Approach 1: Graph Conversion + BFS

class Solution {

    public int countPairs(TreeNode root, int distance) {
        Map> graph = new HashMap<>();
        Set leafNodes = new HashSet<>();

        traverseTree(root, null, graph, leafNodes);

        int ans = 0;

        for (TreeNode leaf : leafNodes) {
            Queue bfsQueue = new LinkedList<>();
            Set seen = new HashSet<>();
            bfsQueue.add(leaf);
            seen.add(leaf);
            // Go through all nodes that are within the given distance of
            // the current leaf node
            for (int i = 0; i <= distance; i++) {
                // Clear all nodes in the queue (distance i away from leaf node)
                // Add the nodes' neighbors (distance i+1 away from leaf node)
                int size = bfsQueue.size();
                for (int j = 0; j < size; j++) {
                    // If current node is a new leaf node, add the found pair to our count
                    TreeNode currNode = bfsQueue.remove();
                    if (leafNodes.contains(currNode) && currNode != leaf) {
                        ans++;
                    }
                    if (graph.containsKey(currNode)) {
                        for (TreeNode neighbor : graph.get(currNode)) {
                            if (!seen.contains(neighbor)) {
                                bfsQueue.add(neighbor);
                                seen.add(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

    private void traverseTree(
        TreeNode currNode,
        TreeNode prevNode,
        Map> graph,
        Set leafNodes
    ) {
        if (currNode == null) {
            return;
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.add(currNode);
        }
        if (prevNode != null) {
            graph.computeIfAbsent(prevNode, k -> new ArrayList());
            graph.get(prevNode).add(currNode);
            graph.computeIfAbsent(currNode, k -> new ArrayList());
            graph.get(currNode).add(prevNode);
        }
        traverseTree(currNode.left, currNode, graph, leafNodes);
        traverseTree(currNode.right, currNode, graph, leafNodes);
    }
}
                

Time Complexity: O(n^2) and Space Complexity: O(n)

Number of Good Leaf Nodes Pairs

The problem Number of Good Leaf Nodes Pairs is a challenging binary tree problem. It focuses on identifying pairs of leaf nodes where the sum of distances between them does not exceed a given threshold.

Problem Statement

Given the root of a binary tree and an integer distance, return the number of pairs of leaf nodes such that the sum of the distances between them is less than or equal to distance.

Key points:

• A "leaf node" is a node with no children.
• The "distance" between two nodes is the number of edges on the path connecting them.

Approach to Solve the Problem

The solution involves recursive traversal of the binary tree while maintaining the distances between leaf nodes. We combine results from the left and right subtrees to count valid pairs efficiently.

Steps to Solve:

1. Perform a depth-first search (DFS) on the tree.
2. At each node, collect the distances of leaf nodes from the current node.
3. Combine the leaf distances from the left and right subtrees to count valid pairs.
4. Return the total number of good leaf node pairs.

Implementation

Here is the Python implementation:

class Solution:
    def countPairs(self, root, distance):
        self.result = 0

        def dfs(node):
            if not node:
                return []
            if not node.left and not node.right:
                return [1]
            
            left_distances = dfs(node.left)
            right_distances = dfs(node.right)

            # Count good pairs
            for l in left_distances:
                for r in right_distances:
                    if l + r <= distance:
                        self.result += 1

            # Increment distances and return
            return [d + 1 for d in left_distances + right_distances if d + 1 < distance]

        dfs(root)
        return self.result
        

Here is a Java implementation:

class Solution {
    private int result = 0;

    public int countPairs(TreeNode root, int distance) {
        dfs(root, distance);
        return result;
    }

    private List dfs(TreeNode node, int distance) {
        if (node == null) return new ArrayList<>();
        if (node.left == null && node.right == null) {
            List leafDistances = new ArrayList<>();
            leafDistances.add(1);
            return leafDistances;
        }

        List leftDistances = dfs(node.left, distance);
        List rightDistances = dfs(node.right, distance);

        // Count good pairs
        for (int l : leftDistances) {
            for (int r : rightDistances) {
                if (l + r <= distance) result++;
            }
        }

        // Increment distances and return
        List newDistances = new ArrayList<>();
        for (int d : leftDistances) {
            if (d + 1 < distance) newDistances.add(d + 1);
        }
        for (int d : rightDistances) {
            if (d + 1 < distance) newDistances.add(d + 1);
        }
        return newDistances;
    }
}
        

Example

Consider the binary tree:

            Tree Structure:
                1
               / \
              2   3
             / \   \
            4   5   6
        

With distance = 3:

• Good pairs are: (4, 5), (4, 6), and (5, 6).
• The result is 3.

Complexity Analysis

Time Complexity: O(n²), where n is the number of nodes in the tree. In the worst case, each pair of leaf nodes is checked.

Space Complexity: O(h), where h is the height of the tree. This accounts for the recursive call stack.

Applications

• Used in networking to calculate communication limits between nodes.
• Helps in analyzing distances between nodes in hierarchical systems.
• Applies to graph-based problems with constraints on path lengths.

Conclusion

The problem Number of Good Leaf Nodes Pairs challenges your understanding of binary tree traversal and recursive logic. By carefully combining results from subtrees, it is possible to solve the problem efficiently while adhering to the distance constraint.

Practice similar problems to enhance your problem-solving skills in tree-based algorithms.