[ Data Structures with Java ] Section 17.2 : Iterative Tree Traversal

Preface :
We have observed the power of iterators to scan the elements in a LinkedList or ArrayList collection. Traversing the nodes in a binary tree is more difficult because a tree is a nonlinear structure and there is no one traversal order. Section 16.3 discuss recursive algorithms for performing a preorder, inorder and postorder scan in a tree. The problem with each of these traversal algorithms is that there is no escape from the recursive process util it completes. We cannot easily stop the scan, examine the contents of a node, and then continue the scan at another node in the tree. We need an iterative process to implement a binary tree iterator. Once choice would be a level-order scan using a queue. As we will discover with binary search trees, an iterator version of a recursive scan is a better choice.

Iterative Tree Traversal :
In this section, we will implement an iterator using an iterative inorder scan. Creating iterators with a preorder and a postorder iterative scan can be your practices. You are familiar with iterators and Iterator interface from our discussion of the LinkedList class. Our binary tree iterator implements the interface.To provide an iterator scan of the elements, we use a stack to hold the nodes that have been passed but not visited. In this way, we can simulate the running time system, which uses a stack to hold the recursive calls that are made during an inorder interator scan of the tree. Because it is our stack, we can halt at any time, access a node, and then continue by popping the stack to pick up the scan. Below is the implementation of class InorderIterator :

- InorderIterator.java : Iterator used to traversal the binary tree.

view plaincopy to clipboardprint?

1. package DSwJ.S17;  
2.   
3. import java.util.Iterator;  
4. import java.util.NoSuchElementException;  
5.   
6. import DSwJ.S14.ALStack;  
7. import DSwJ.S16.TNode;  
8.   
9. public class InorderIterator  implements Iterator{  
10.     private ALStack> s = null;  
11.     private TNode curr;  
12.       
13.     public InorderIterator(TNode root) {  
14.         s = new ALStack>();  
15.         curr = goFarLeft(root);  
16.     }  
17.       
18.     @Override  
19.     public boolean hasNext() {  
20.         if(curr!=null) return true;  
21.         return false;  
22.     }  
23.   
24.     @Override  
25.     public T next() {  
26.         if(curr==null)  
27.             throw new NoSuchElementException("InorderScan: no elements remaining!");  
28.         T rtValue = curr.nodeValue;  
29.         if(curr.right!=null) {  
30.             curr = goFarLeft(curr.right);  
31.         } else if(!s.isEmpty()){  
32.             curr = s.pop();  
33.         } else {  
34.             curr = null;  
35.         }  
36.         return rtValue;  
37.     }  
38.   
39.     @Override  
40.     public void remove() {  
41.         throw new UnsupportedOperationException("Not support remove action!");  
42.     }  
43.   
44.     /** 
45.      * This method is critical to finding the "next" node. 
46.      * @param t 
47.      * @return 
48.      */  
49.     private TNode goFarLeft(TNode t) {  
50.         if(t==null)  
51.             return null;  
52.         while(t.left!=null) {  
53.             s.push(t);  
54.             t = t.left;  
55.         }  
56.         return t;  
57.     }  
58. }  

Inorder Iterative Traversal :
The inorder iterative traversal emulates a recursive scan. Use of a stack is a key feature. Nodes enter the stack when we move down the tree from the current iterator (node) position to the node that references the "next" iterator position. In this way, the iterative algorithm can "remember" each intermediate node on the path so it can come back up the tree and visit the node at a later point. To do this, push on a stack the references to each of the nodes that are discovered on the path to the "next" element.
An iterative scan begins at the leftmost node in the tree (inorder scan). The starting point is found by starting at the root and following the chain of left children until we locate a node with an empty left subtree. An iterator initially references this node. The root and all intermediate nodes on the path of left children are pushed on the stack. The iterative traversal of the tree is based on the following set of rules :

Rule1 : At each node, capture the value of the node.
Rule2 : If the right branch of the node is not empty, move to the right child and then traverse the path of the left children until we locate a node with a null left subtree. The traversal identifies the node as the "next" node. Push on the stack a reference to the right child and each intermediate node on the path.
Rule3 : If the right branch of the node is empty, we have completed the scan of the node's left branch, the node itself, and its right branch. The next node to visit is on the stack. If the stack is not empty, pop it to determine the next node in the scan. If the stack is empty, all nodes have been visited and we terminate the scan.

Let us trace the iterative inorder traversal of nodes in the following character tree. The order of visits to the nodes is BFDAEC. We organize the trace around the order in which nodes are scanned. In this way, you can understand how the algorithm uses the stack and the traversal rules to proceed from a "current" scan position to the "next" scan position :
- Scan 'B' and then 'F'

The iterator is initially positioned at node B. We arrive there by starting at the root and traversing the path of left children. The one node on this path, namely the root A, is placed on the stack (a). By rule 2, the next element is node F, which is the leftmost node in the right subtree of B. The path to F encounters node D which is pushed on the stack (b) :

- Scan 'D' and then 'A'

Node F has no right child. By rule 3, the next node is D, which is popped from the stack (c). The same rule 3 applies to D. The next node is A (d) :

- Scan 'E' then 'C'

From node A, use rule2 to visit the next node E. Node C is on the path from A to E and thus is pushed on the stack (e). By rule3, the next node C, which is popped from the stack (f) :