## Wednesday, June 16, 2010

### Tree Traversal

Given the following tree, how would you print out the nodes in the following order: 0, 1, 2, 3, 4, 5? (interview question)
```     0
/   \
1     2
/ \   /
3   4 5
```
The problem can be solved with breadth-first (level-order) traversal, using an intermediate queue and iteration:
```public void breadthFirstIterative(Node root){
while(!q.isEmpty()){
Node node = q.poll();
System.out.println(node.data);
if(node.left != null){
}
if(node.right != null){
}
}
}
```
You can also solve it using recursion, but this is not efficient and not recommended.
```public void breadthFirstRecursive(Node root) {
Map<Integer, List<Node>> map =
new TreeMap<Integer, List<Node>>();
for (int i : map.keySet()) {
List<Node> nodes = map.get(i);
for(Node node : nodes){
System.out.println(node);
}
}
}

Map<Integer, List<Node>> map,
int level) {
List<Node> nodes = map.get(level);
if (nodes == null) {
nodes = new ArrayList<Node>();
map.put(level, nodes);
}
if (node.left != null) {
}
if (node.right != null) {
}
}
```
Depth-first Traversal:
Just for completeness, I will also show you the algorithm for depth-first traversal, which will not print out 0, 1, 2, 3, 4, 5 but will print out 0, 1, 3, 4, 2, 5. Here is the algorithm using a stack and iteration:
```public void depthFirstIterative(Node root) {
Stack<Node> s = new Stack<Node>();
s.push(root);
while (!s.isEmpty()) {
Node node = s.pop();
System.out.println(node);
if (node.right != null) {
s.push(node.right);
}
if (node.left != null) {
s.push(node.left);
}
}
}
```
You can also solve it using recursion:
```
public void depthFirstRecursive(Node root) {
System.out.println(root);
if (root.left != null) {
depthFirstRecursive(root.left);
}
if (root.right != null) {
depthFirstRecursive(root.right);
}
}
```