Interview Question

Software Engineer Interview Santa Clara, CA

Find a longest path in a tree.

Answer

Interview Answer

1 Answer

0

List<Node> longestPath(Node node) {
    List<Node> path = new ArrayList<Node>();
    path.add(node);

    List<Node> longestChildPath = new ArrayList<Node>();
    for(Node child: node.children()) {
        List<Node> childPath = longestPath(child);
        if (longestChildPath == null || childPath.size() > longestChildPath) {
            longestChildPath = childPath;
        }
    }

    path.addAll(longestChildPath);
    return path;
}

Anonymous on Jul 14, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.