Tuesday 14 April 2020

Algorithm for Level Order Tree Traversals : Iterative Model(Non-Recursive way)



import java.util.LinkedList;
import java.util.Queue;

//Level Order Tree Traversals : Iterative Model(Non-Recursive way)

class BinaryTreeLevelOrderTraversalIterativeModel {

      class TreeNode {
            TreeNode left, right;
            int data; // considering integer data.
      
            public TreeNode(int dataItem) {
                  this.data = dataItem;
                  left = null;
                  right = null;
            }
      }
      
       TreeNode root;
       BinaryTreeLevelOrderTraversalIterativeModel() {
             root = null;
       }
      
       void printLevelOrderTraversal(TreeNode treeNode) {
             if(treeNode == null)
                    return;
            
             //Level0, Level1, Level2...
             Queue<TreeNode> q = new LinkedList<TreeNode>();
             q.offer(root);
             while(!q.isEmpty()) {
                    TreeNode temp = q.poll();
                    System.out.println(temp.data);
                   
                    if(temp.left != null) {
                          q.offer(temp.left);
                    }
                   
                    if(temp.right != null) {
                          q.offer(temp.right);
                    }
             }


       }
      
       void printLevelOrder() {
             printLevelOrderTraversal(root);
       }

       public static void main(String[] args) {
             BinaryTreeLevelOrderTraversalIterativeModel tree = new BinaryTreeLevelOrderTraversalIterativeModel();
             tree.root = new TreeNode(1);
       
             tree.root.left = new TreeNode(2);
             tree.root.right = new TreeNode(3);
       
             tree.root.left.left = new TreeNode(4);
             tree.root.left.right = new TreeNode(5);
       
             tree.root.right.left = new TreeNode(6);
             tree.root.right.right = new TreeNode(7);
       
             tree.printLevelOrder();
       }

}

//Time Complexity: O(n). Space Complexity: O(n).


Thanks..!!

No comments:

Post a Comment