4
\$\begingroup\$

In an interview I was asked to write Java code to build a tree and return the root, given a list of edges. It was a fairly open ended question where the interviewer left all the decisions up to me.

I used to following logic: edges of trees are directional, so I made a Pair class which has a start node and an end node. I go over the list of Pairs and I made a HashMap from it in a way that the each key in the map is kept as a node and then the value in the map is the set of its children. Then for each key I iterate over the sets of children and see if that node is a child of any other node. If it is then it is not the node we are looking for, if a node isn't in any children set then it is the root.

There are of course edge cases where there can be a cycle within the tree, so let's say some node connects to the root. Or another case is that the root might be fine, but there are cycles within the children nodes. Or there is another case where there can be multiple distinct trees in the list of edges.

I tried to code this up in the following manner and I have tried to add comments wherever applicable so that the code can be understood more:

import java.util.*;

public class TreeBuilder {
    public static Node returnRoot(List<Pair> input){
          if(input == null || input.size() == 0){
              throw new IllegalArgumentException("Input is null or doesn't contain any elements");
          }

          // Create a list of roots, in case there are multiple roots present
          List<Node> roots = new ArrayList<>();

          // This boolean checks if there are edges pointing to a particular node
          boolean isPresent = false;
          HashMap<Node, HashSet<Node>> adjList = buildList(input);

          // iterate over each key of the hash map (which is the tree) and check if there are any edges pointing to it
          for(Node keyItr: adjList.keySet()) {
              for (HashSet<Node> setItr : adjList.values()) {
                  if (setItr.contains(keyItr)) {
                      isPresent = true;
                      break;
                  }
              }

              // if there were no edges pointing to this node, add it as a root
              if (!isPresent) {
                  roots.add(keyItr);
                  // Ideally we would return the keyItr here as the root
                  // but we continue to check if there are multiple roots in the input data
              }
              isPresent = false;
          }

          // only one root is found
          if(roots.size() == 1){
              // check if there are cycles within the children of this tree and return the root
              checkChildCycles(adjList);
              return roots.get(0);
          }

          // there is a cycle with the root
          else if(roots.size() == 0) {
              throw new IllegalArgumentException("Input pairs contain a cycle with the root");
          }

          // there are multiple roots
          else{
              throw new IllegalArgumentException("Input pairs contains multiple ("+ roots.size() + ") roots");
          }
      }

      public static HashMap<Node, HashSet<Node>> buildList(List<Pair> input){
        HashSet<Node> childSet;
        HashMap<Node, HashSet<Node>> adjList = new HashMap<>();
        for(Pair i: input){
            // if this subtree exists, add the child to that
            if(adjList.containsKey(i.start)){
                childSet = adjList.get(i.start);
                childSet.add(i.end);
                adjList.put(i.start, childSet);
            }
            // create a new subtree
            else{
                HashSet<Node> newSet = new HashSet<>();
                newSet.add(i.end);
                adjList.put(i.start, newSet);
            }
        }
        return adjList;
    }

    public static void checkChildCycles(HashMap<Node, HashSet<Node>> tree){
        int childOccurance = 0;
        // for each set
        for(HashSet<Node> setItr: tree.values()){
            // for each node in set
            for(Node x : setItr){
                // check against each value set to find occurrences
                for(HashSet<Node> checkSets: tree.values()){
                    if(checkSets.contains(x)){
                        childOccurance++;
                        if(childOccurance > 1){
                            throw new IllegalArgumentException("Input pairs contain cycle with child nodes");
                        }
                    }
                }
                childOccurance = 0;
            }
        }
    }

    public static void main(String[] args){
        List<Pair> input = new ArrayList<>();
        Node r1 = new Node("r1");
        Node c11 = new Node("c11");
        Node c12 = new Node("c12");
        Node c13 = new Node("c13");
        Node c111 = new Node("c111");
        Node c112 = new Node("c112");
        Node c121 = new Node("c121");
        // add these nodes to pairs of the tree as edges
        Pair p1 = new Pair(r1,c11);
        Pair p2 = new Pair(r1,c12);
        Pair p3 = new Pair(r1,c13);
        Pair p4 = new Pair(c11,c111);
        Pair p5 = new Pair(c11,c112);
        Pair p6 = new Pair(c12, c121);
        // add these pairs to our input list of edges
        input.add(p4); input.add(p5); input.add(p6);
        input.add(p1); input.add(p2); input.add(p3);

        // to test edge cases

        // pair that makes cycle with root
        // Pair p7 = new Pair (c121, r1);
        // input.add(p7);

        // pair that makes cycle with children
        // Pair p8 = new Pair(c121, c112);
        // input.add(p8);

        // 2 nodes to create 2 trees
        //Node d1 = new Node("d1");
        //Node d2 = new Node("d2");
        // pair that makes 2 trees / 2 roots
        //Pair p9 = new Pair (d1, d2);
        //input.add(p9);


        // execute the function
        try{
            System.out.println(returnRoot(input).data);
        }
        catch(Exception ex) {
            System.out.println(ex.getMessage());
        }
    }
}

class Node{
    String data;

    Node(String data){
        this.data = data;
    }
}

class Pair{
    Node start;
    Node end;

    Pair(Node start, Node end){
        this.start = start;
        this.end = end;
    }
}

How does this solution look? I am also looking for feedback on naming convention and coding style as well. I can clarify more if needed. Appreciate the help in advance.

\$\endgroup\$
4
\$\begingroup\$

Major point number 1: if the question is:

build a tree and return the root

Do we expect a single data node as a result? Or de we expect a root node of a tree, from which we can traverse the entire tree if we want?

I would expect an actual tree node as the result.

The major questions I would then ask the interviewers is: Can I assume that the edges form a binairy tree? Or should we allow an arbitrary amount of child nodes? Should it be an ordered tree? Can I assume correct input (and document it ofcourse) or should I check if the input will form a valid tree?

They might answer that you can choose for yourself. In which case I would just choose the easiest one to implement and explain what would might have to change if the requirements were different.

So let's say ordering doesn't matter, and that a tree can have multiple children. Then the Node class could look something like this:

public class Node {
    private final String data;
    private List<Node> children = new ArrayList<>();

    public Node(String data){
        this.data = data;
    }

    public void addChild(Node node){
        children.add(node);
    }

    public List<Node> getChildren(){
        return children;
    }

    public String getData(){
        return data;
    }
}

That way we can just go over all your Pairs of Nodes and add the second one to the first to actually build our tree. The only thing left after that is to figure out which is the root node.

The actual treebuilding implementation would then look something like this:

/**
* This method will attempt to build a tree from the given edges.
* The result is the root node of the tree. (i.e. the Node that is not a child node of any other Node).
* If there are multiple root Nodes it is undefined which one will be returned.
* In case there are no root nodes an IllegalArgumentException is thrown.
*/
public static Node buildTree(List<Pair> edges) {
    Set<Node> rootNodes = new HashSet<>();
    Set<Node> childNodes = new HashSet<>();

    for(Pair pair: edges){
        pair.start.addChild(pair.end);

        rootNodes.remove(pair.end);
        childNodes.add(pair.end);
        if (!childNodes.contains(pair.start)) {
            rootNodes.add(pair.start);
        }
    }

    if (rootNodes.isEmpty()) {
        throw new IllegalArgumentException("Input pairs contain a cycle with the root");
    }

    return rootNodes.iterator().next();
}

I'd also have answers ready to the alternative requirements I mentioned earlier. For example: if we should not allow multiple root nodes as input we just need to add the following check:

if(rootNodes.size()>1) {
    throw new IllegalArgumentException("Input pairs contains multiple ("+ roots.size() + ") roots");
}

right before returning the root node.

Another example: if the ordering is important. I would define Comparator for Node and use Collections.sort() right after adding a node (if it wasn't the first node added).


Now that we got the interview question handled let's look at your code style.

Interface > Concrete Implementation

You did it correctly on this line:

List<Node> roots = new ArrayList<>();

Where you use the more general List as type for roots. But the same applies for Set over HashSet or Map over HashMap. For example

HashMap<Node, HashSet<Node>> adjList = buildList(input);

should be

Map<Node, Set<Node>> adjList = buildList(input);

The only point where you want to use the concrete implementation (for example ArrayList is when you actually instantiate the list (like you did correctly in your roots variable).

comments should say why, not what

Comments that say what you do are redundant. If they are not, then you should probably rename some variables/methods/... so that they become redundant. And once redundant they should be removed.

For example:

// check if there are cycles within the children of this tree and return the root
checkChildCycles(adjList);
return roots.get(0);

What value does this comment really add to your code? Isn't it clear enough what you do here?

Another examle:

  // This boolean checks if there are edges pointing to a particular node
  boolean isPresent = false;

Now I got 2 problems with this comment. First is that I still don't really understood what the variable means. And second that it shows that the name is badly chosen. What is present if the variable is true? Or what is absent if it isn't?

What happens if we rename it to hasChildNode? Or even better, invert the logic and call it isRootNode. That way, once we find a parent node of the node we're checking we say: isRootNode = false. And The following check also reads naturally:

if (isRootNode) {
    roots.add(keyItr);
}

encapsulation + immutability

Immutability is nice. It often makes things easier to reason about and prevents silly mistakes. Some purists would even go all the way and make everything immutable, I usually stick with: "start immutable, and make it mutable if it's logical to change the state".

Also encapsulate all information about how a class is implemented inside that class. If you ever change your mind about an implementation you're going to regret those public/package/protected variables.

A good rule of thumb is that variables should always be private and should start only with getters. Add setters only if they make sense.

Take a look at my implementation for the Node class for example. The data is set in the constructor only and never changes after. It's possible to add a child but not to remove them directly. It actually is possible to remove one by first geting the list and then remove it from there. So it's not entirely immutable. This implementation is good enough for me. Otherwise you'd have more overhead with either cloning the list on each call to getChildren or have more trouble creating a Node with an immutable list instead.

naming

One of the hardest things you have to do as a programmer is finding good meaningful names for everything.

I already pointed out the isPresent variable but there a few more that could be improved.

Take this piece of code for example:

 for(Node keyItr: adjList.keySet()) {
      for (HashSet<Node> setItr : adjList.values()) {
          if (setItr.contains(keyItr)) {
              isPresent = true;
              break;
          }
      }

If I would randomly open your class file and find these loops I wouldn't understand a thing of what happens. Let's compare it to this:

for(Node potentialRootNode: childMap.keySet()){
    for(Set<Node> : children : childMap.values()) {
        if(children.contains(potentialRootNode){
            isRootNode = false;
            break;
        }
    }

It's still out of context but at least now we can guess that we're looking for a root node.

scope

Variables should be declared as close to where they're used as possible. And their scope should be limited to as small as possible. A good example is the childOccurance variable in this method:

public static void checkChildCycles(HashMap<Node, HashSet<Node>> tree){
    int childOccurance = 0;
    for(HashSet<Node> setItr: tree.values()){
        for(Node x : setItr){
            for(HashSet<Node> checkSets: tree.values()){
                if(checkSets.contains(x)){
                    childOccurance++;
                    if(childOccurance > 1){
                        throw new IllegalArgumentException("Input pairs contain cycle with child nodes");
                    }
                }
            }
            childOccurance = 0;
        }
    }
}

The fact that it's declared outside of the for loops implies that it might be used afterwards. If we put it inside the second for loop instead, we don't even need to reset it again at the end:

public static void checkChildCycles(HashMap<Node, HashSet<Node>> tree){
    for(HashSet<Node> setItr: tree.values()){
        for(Node x : setItr){
            int childOccurance = 0;
            for(HashSet<Node> checkSets: tree.values()){
                if(checkSets.contains(x)){
                    childOccurance++;
                    if(childOccurance > 1){
                        throw new IllegalArgumentException("Input pairs contain cycle with child nodes");
                    }
                }
            }
        }
    }
}

If the names were chosen better and the method wasn't nested 5 levels deep this could actually become easier to follow now :)


As a final note I want to point out that your cycle check also throws exceptions on diamond shapes. This is probably also what you intended but they're technically not cycles, in that it's not a loop.

\$\endgroup\$
  • \$\begingroup\$ Wow! Thanks a lot for such in depth feedback. I really appreciate it. I had talked to the interviewer and told him that the hashmap that is returned from the buildList method in my code is the tree where each node represents the parent and it's adjacency list contains the children. The main goal was to return the root, rather than traverse the tree. I could probably make another method to traverse the tree. I do have an issue to come up with good names for methods and variables, and I will surely keep in mind the tips that you gave. \$\endgroup\$ – Sid May 2 '17 at 19:43
1
\$\begingroup\$

There's not much to add to @Imus excellent answer, apart from a little naming advice:

your Pair is in fact an edge in a graph. You even call the collection edges. So really Pair should be renamed to Edge to correctly grasp the business object behind it. (BTW: as an interviewer in a rush, that would probably the first point of criticism I came up with.)

\$\endgroup\$
  • \$\begingroup\$ I actually did think of exactly this, but completely forgot to add it into my answer. Upvote for pointing it out :) \$\endgroup\$ – Imus May 7 '17 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.