Interview Question

Interview Sunnyvale, CA

Given the root node of a tree, write two Java programs to

  visit all nodes of the tree, one in a depth-first fashion and the other in a breadth-first fashion, both without using recursion. Assume a node is represented by a class named Node, which has a method children() that returns a list of child nodes. Call node.visit() to visit a node.
Tags:
java, tree
Answer

Interview Answer

1 Answer

0

DFS: Use stack Stack stack = new Stack(); stack.push(root); while(!stack.empty()){ Node node = stack.pop(); List<Node>children = node.children(); if(children == null || children.size() == 0) continue; for(Node child in children) stack.push(child); } BFS: Use queue Queue<Node> queue = new Queue(); queue.offer(root); while(queue.peek() != null){ Node node = queue.remove(); List<Node> children = node.children(); if(children == null || children.size() == 0) continue; for(Node child in children) queue.offer(child); }

H on Mar 13, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.