educative.io

Alternative solution with BFS and Adjacency List

Courses
,
#1

I would not necessarily classify this as a DFS problem and if so, I think it is worth mentioning IDDFS as an alternative to recursion because for senior role interviews, recursion can be rejected as a solution (with Java).
Hereby I solved it with BFS and Adjacency List.

import java.util.*;
public class TreeDiameter{
    public static int diameterOfBinaryTree(BinaryTreeNode root) {
        Deque<Pair> q = new LinkedList<>();
        List<Pair> list = new ArrayList<>();
        q.offer(new Pair(null, root));
       
        while (!q.isEmpty()) {
            Pair curr = q.poll();
            list.add(curr);
            if (curr.node.left != null) q.offer(new Pair(curr, curr.node.left));
            if (curr.node.right != null) q.offer(new Pair(curr, curr.node.right));
        }

        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (Pair el : list) {
            ArrayList<Integer> neighbors = new ArrayList<>();
            if (el.parent != null) {
                neighbors.add(el.parent.node.data);
            }
            if (el.node.left != null) {
                neighbors.add(el.node.left.data);
            }
            if (el.node.right != null) {
                neighbors.add(el.node.right.data);
            }
            graph.put(el.node.data, neighbors);
        }

        var max = 0;
        for (Map.Entry<Integer, ArrayList<Integer>> integerArrayListEntry : graph.entrySet()) {
            Deque<Pair2> q1 = new LinkedList<>();
            HashSet<Integer> visited = new HashSet<>();
            q1.add(new Pair2(null, integerArrayListEntry.getKey()));
            visited.add(integerArrayListEntry.getKey());
            while (!q1.isEmpty()) {
                int tmp = 0;
                Pair2 current = q1.poll();
                visited.add(current.value);

                Pair2 tail = current;
                while (tail.parent != null) {
                    tmp++;
                    tail = tail.parent;
                }

                max = Math.max(max, tmp);

                for (Integer integer : graph.get(current.value)) {
                    if (!visited.contains(integer)) {
                        q1.offer(new Pair2(current, integer));
                    }
                }
            }

        }

        return max;
    }

    public static class Pair2 {
        Pair2 parent;
        int value;

        Pair2(Pair2 parent, int value) {
            this.parent = parent;
            this.value = value;

        }
    }

    public static class Pair {
        Pair parent;
        BinaryTreeNode node;

        Pair(Pair parent, BinaryTreeNode node) {
            this.parent = parent;
            this.node = node;
        }
    }
}

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Diameter of Binary Tree - Grokking Coding Interview Patterns in Java

#2

Hello @Davide_Pugliese

Thank you for sharing your solution to the Diameter of Binary Tree problem using BFS and an adjacency list. It’s great to see different perspectives and approaches to solving problems.

While BFS is a valid approach, it may have a higher space complexity in working compared to DFS, especially when using an adjacency list to represent the tree. DFS can also be more intuitive for solving this specific problem, as it allows for traversing deeper into the tree and finding the longest path, since we are interesting in finding the diameter.

That being said, it’s important to understand and be familiar with different approaches and their trade-offs. Your solution is a valuable addition to your understanding of the problem, and I appreciate your effort and ideas. Keep up the good work!

Also, I agree that IDDFS is a valuable technique that can be useful in situations.

Happy Learning!

#3

I understand your point, however in real world, in some cases even though one solution has better time complexity is not necessarily better.
In Java with your solution you would need to test the algo with a specific JVM (OpenJDK, Oracle JDK, Corretto, whatever) and then set a stack size that is large enough to accommodate most scenarios.
When you manage the stack (queue in this case) yourself this is not an issue.
That is why when interviewing for Java positions they prefer solutions which do not involve recursion.
I am not talking about Google, I am talking about Oracle, UBS, etc.
That is why I am not saying your solution is bad either, I am just saying you should provide an iterative version for those interviews when you are asked to solve the problem without recursion.

Course: Grokking the Behavioral Interview - Learn Interactively
Lesson: Body Language - Grokking the Behavioral Interview

#6

Hi Davide,

You make a strong point about the limitations of recursive solutions.

We have taken this on board in our ongoing incremental improvement activity. We will update you as and when we add iterative solutions as alternatives to recursive solutions.

Thank you for taking the time to provide this feedback and following up with us.

1 Like