04/05/2018

[Java] Iterative inorder tree traversal

Some time ago we saw different ways to visit a binary tree, today we take a spin on one of those and implement an inorder traversal without recursion.

You can check the code on my Gist.

 //iterative inorder visit, use a stack as helper structure  
   private static List<Integer> doInorderVisitIterative(BST root, List<Integer> out){  
     if(root == null) return out;  
   
     BST curr = root;  
     Stack<BST> s = new Stack<>();  
   
     //keep looping as long as we have at least one valid element  
     while(!s.isEmpty() || curr != null){  
       //if current element is not null, keep stacking the left children  
       if(curr != null){  
         s.push(curr);  
         curr = curr.left;  
       }  
       //when we get a null, move up the tree (in stack view) again, visit the node, and switch to the right subtree  
       else{  
         curr = s.pop();  
         out.add(curr.getVal());  
         curr = curr.right;  
       }  
     }  
   
     return out;  
   }  



No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.