0 / \ 1 2 / \ / 3 4 5

**Breadth-first Traversal:**

The problem can be solved with breadth-first (level-order) traversal, using an intermediate queue and iteration:

public void breadthFirstIterative(Node root){ Queue<Node> q = new LinkedList<Node>(); q.add(root); while(!q.isEmpty()){ Node node = q.poll(); System.out.println(node.data); if(node.left != null){ q.add(node.left); } if(node.right != null){ q.add(node.right); } } }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>>(); breadthFirst2(root, map, 0); for (int i : map.keySet()) { List<Node> nodes = map.get(i); for(Node node : nodes){ System.out.println(node); } } } private void breadthFirst2(Node 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); } nodes.add(node); if (node.left != null) { breadthFirst2(node.left, map, level + 1); } if (node.right != null) { breadthFirst2(node.right, map, level + 1); } }

**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); } }

## No comments:

## Post a Comment