Motorola Mobility

  www.motorola.com
  www.motorola.com

Interview Question

Software Engineer Intern 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.