CODEWITHSUNDEEP
javatree
Vandan Patel
Vandan Patel

Reputation: 1022

How to find the depth of a tree iteratively in Java?

In an interview, I was asked to find the depth of the tree. I did it recursively, but then interviewer asked me to do it using iteration. I did my best, but i don't think he looked quite convinced. can anyone write the pseudo-code here or code would be preferable...Thanks for reading the post.

Upvotes: 1

Views: 2718

Answers (3)

ptomli
ptomli

Reputation: 11818

Tree<Object> tree = ...; // source

class NodeMarker {
    public NodeMarker(TreeNode node, int depth) { ... }
    public TreeNode node;
    public int depth;
}

int depth = 0;
List<NodeMarker> stack = new LinkedList<NodeMarker>();
for (TreeNode node : tree.getChildren())
    stack.add(new NodeMarker(node, 1);

while (stack.size() > 1) {
    NodeMarker marker = stack.get(0);
    if (depth < marker.depth)
        depth = marker.depth;

    if (marker.node.hasChildren())
        for (TreeNode node : marker.node.getChildren())
            stack.add(new NodeMarker(node, marker.depth + 1);
}

Upvotes: 1

Dan
Dan

Reputation: 10786

Iteration rather than recursion means that is you go down the tree, rather than having each function call spawn two new function calls, you can store each member of the layer in an array. Try starting with a (one element) array containing a pointer to the root. Then, in a loop (I'd just use a while (1)) iterate over that array (currentLayer) and create a new array (nextLayer) and add the children of each element in currentLayer to nextLayer. If nextlayer is empty, you're now at the deepest layer, otherwise increment depth by one, copy nextLayer to currentLayer, and do it again.

Upvotes: 0

Steve J
Steve J

Reputation: 2674

Check the answer provided at Way to go from recursion to iteration. Bottom line is that you don't have to solve the problem twice. If you have a perfectly good recursive algorithm, then transform it into an iteration.

Upvotes: 2

Related Questions