fork download
copy 
  1. /*Tree Traversal:
  2. ->Process of visiting each node in the tree exactly once in some order.
  3.  
  4. ->Visit:-Reading/Processing data in node.
  5.  
  6. ->2-types:
  7. ->Breadth First Traversal:Visit all nodes at same level(left to right)
  8.                           ->Also called level order traversal
  9. ->Depth First Traversal:-First visit all nodes in left subtree and then right subtree.
  10.                         1.Preorder(root,left,right)(data,left,right)
  11.                         2.Inorder(left,root,right)(left,data,right)
  12.                         3.Postorder(left,right,root)(left,right,data)
  13. ->Tree: start from the root
  14.                             ->Preorder:-FDBACEJGIHK
  15.                             ->InOrder:-ABCDEFGHIJK
  16.                             ->Postorder:-ACBEDHIGKJF
  17.           F
  18.          / \
  19.         D   J
  20.        / \  / \
  21.       B   E G  K
  22.      / \    \
  23.     A   C    I
  24.              /
  25.              H
  26.  */
  27. import java.util.Queue;
  28. import java.util.LinkedList;
  29. import java.util.Stack;
  30. import java.lang.*;
  31. import java.io.*;
  32. import java.util.logging.Level;
  33.  
  34. class LevelOrderNode
  35. {
  36.     int data;
  37.     LevelOrderNode left;
  38.     LevelOrderNode right;
  39.     LevelOrderNode()
  40.     {
  41.         left=null;
  42.         right=null;
  43.     }
  44. }
  45.  
  46.  
  47.  class BinaryTreeTraversal {
  48.  
  49.     //Global variable that will store address of root node
  50.  
  51.     public static LevelOrderNode root=null;
  52.  
  53.  
  54.     public static LevelOrderNode GetNewNode(int data)
  55.     {
  56.         LevelOrderNode newNode=new LevelOrderNode();
  57.         newNode.data=data;
  58.         newNode.left=null;
  59.         newNode.right=null;
  60.         return newNode;
  61.     }
  62.  
  63.  
  64.     //Recursive Version of Adding a node to binary search tree
  65.     public static LevelOrderNode Add_recursive(LevelOrderNode root,int data)
  66.     {
  67.         if(root==null)
  68.         {
  69.             //Empty tree
  70.             root=GetNewNode(data);
  71.             return root;
  72.         }
  73.         else if(data<=root.data)
  74.         {
  75.             root.left=Add_recursive(root.left,data);
  76.         }
  77.         else
  78.         {
  79.             root.right=Add_recursive(root.right,data);
  80.         }
  81.         return root;
  82.     }
  83.  
  84.     //Iterative Version of Adding Node to a binary search tree
  85.     public static LevelOrderNode Add_Iterative(LevelOrderNode root,int data)
  86.     {
  87.         LevelOrderNode node=new LevelOrderNode();
  88.         node.data=data;
  89.  
  90.         if(root==null)
  91.         {
  92.             root=node;
  93.  
  94.             return root;
  95.         }
  96.         LevelOrderNode parent=null;
  97.         LevelOrderNode current=root;
  98.         while(current!=null)
  99.         {
  100.             parent=current;
  101.             if(current.data<=data)
  102.             {
  103.                 current=current.right;
  104.             }
  105.             else
  106.             {
  107.                 current=current.left;
  108.             }
  109.         }
  110.         if(parent.data<=data)
  111.         {
  112.             parent.right=node;
  113.         }
  114.         else
  115.         {
  116.             parent.left=node;
  117.         }
  118.         return root;
  119.     }
  120.  
  121.  
  122.     public static void PreOrder(LevelOrderNode root)
  123.     {
  124.         /*Steps:->first visit root
  125.                 ->Visit left subtree
  126.                 ->Visit right subtree
  127.                 */
  128.         if(root==null)
  129.         {
  130.             return;
  131.         }
  132.         System.out.print(root.data+" ");
  133.         PreOrder(root.left);
  134.         PreOrder(root.right);
  135.  
  136.     }
  137.  
  138.     public static void InOrder(LevelOrderNode root)
  139.     {
  140.         if(root==null)
  141.         {
  142.             return;
  143.  
  144.         }
  145.         InOrder(root.left);
  146.         System.out.print(root.data+" ");
  147.         InOrder(root.right);
  148.     }
  149.  
  150.     public static void PostOrder(LevelOrderNode root)
  151.     {
  152.         if(root==null)
  153.         {
  154.             return;
  155.         }
  156.         PostOrder(root.left);
  157.         PostOrder(root.right);
  158.         System.out.print(root.data+" ");
  159.     }
  160.  
  161.     //Iterative versions of PreOrder,InOrder,PostOrder Traversals
  162.     public static void IterativePreOrder(LevelOrderNode root)
  163.     {
  164.         if(root==null)
  165.         {
  166.             return;
  167.         }
  168.         Stack<LevelOrderNode> s=new Stack<LevelOrderNode>();
  169.         s.push(root);
  170.         while(!s.isEmpty())
  171.         {
  172.             root=s.pop();
  173.             System.out.print(root.data+" ");
  174.             if(root.right!=null)
  175.             {
  176.                 s.push(root);
  177.             }
  178.             if(root.left!=null)
  179.             {
  180.                 s.push(root);
  181.             }
  182.         }
  183.  
  184.     }
  185.  
  186.     public static void IterativeInOrder(LevelOrderNode root)
  187.     {
  188.         if(root==null)
  189.         {
  190.             return;
  191.         }
  192.         Stack<LevelOrderNode> s=new Stack<LevelOrderNode>();
  193.         while(true)
  194.         {
  195.             if(root!=null)
  196.             {
  197.                 s.push(root);
  198.                 root=root.left;
  199.             }
  200.             else
  201.             {
  202.                 if(s.isEmpty())
  203.                 {
  204.                     //Terminating condition
  205.                     break;
  206.                 }
  207.                 root=s.pop();
  208.                 System.out.print(root.data+" ");
  209.                 root=root.right;
  210.             }
  211.  
  212.         }
  213.     }
  214.  
  215.     public static void IterativePostOrder(LevelOrderNode root)
  216.     {
  217.         if(root==null)
  218.         {
  219.             return;
  220.         }
  221.         Stack<LevelOrderNode> s1=new Stack<LevelOrderNode>();
  222.         Stack<LevelOrderNode> s2=new Stack<LevelOrderNode>();
  223.         s1.push(root);
  224.         while(!s1.isEmpty())
  225.         {
  226.             root=s1.pop();
  227.             s2.push(root);
  228.             if(root.left!=null)
  229.             {
  230.                 s1.push(root.left);
  231.             }
  232.             if(root.right!=null)
  233.             {
  234.                 s1.push(root.right);
  235.             }
  236.         }
  237.         while(!s2.isEmpty())
  238.         {
  239.             root=s2.pop();
  240.             System.out.print(root.data);
  241.         }
  242.     }
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.     //This is the code for Level Order Traversal(Breadth First Search)
  250.     public static void LevelOrder_Traverse(LevelOrderNode root)
  251.     {
  252.         //Time complexity of level order traversal:O(n)
  253.  
  254.         //Space complexity of level order traversal:O(1)(best case)
  255.                                        //Worst case:O(n)
  256.         if(root==null)
  257.         {
  258.             return;
  259.         }
  260.         //Here we create queue to store node and its children
  261.         //Queue stores pointer to particular node
  262.         Queue<LevelOrderNode> q = new LinkedList<LevelOrderNode>();
  263.  
  264.  
  265.         //Intially add root node to the queue
  266.         q.add(root);
  267.  
  268.  
  269.         //Run a loop till queue is not empty
  270.         //q.isEmpty() returns true is the queue is empty
  271.         //While there is atleast one discovered node
  272.         while(!q.isEmpty())
  273.         {
  274.             //Object poll()	It is used to retrieves and removes the head of this queue, or returns null if this queue is empty.
  275.             LevelOrderNode current=q.poll();
  276.             System.out.print(current.data);
  277.  
  278.  
  279.             //if left and right child are not null then add them to the queue
  280.             if(current.left!=null)
  281.             {
  282.                 q.add(current.left);
  283.             }
  284.             if(current.right!=null)
  285.             {
  286.                 q.add(current.right);
  287.             }
  288.         }
  289.     }
  290.     public static void main(String[] args)
  291.     {
  292.             root=Add_recursive(root,1);
  293.             root=Add_recursive(root,2);
  294.             root=Add_recursive(root,3);
  295.             root=Add_recursive(root,4);
  296.             root=Add_recursive(root,5);
  297.  
  298.             //printing LevelOrder
  299.             //System.out.print("LevelOrder traversal:");
  300.             //LevelOrder_Traverse(root);
  301.  
  302.             System.out.println();
  303.  
  304.             //Printing PreOrder
  305.             System.out.print("PreOrder traversal:");
  306.             PreOrder(root);
  307.             //System.out.println("Hello");
  308.  
  309.  
  310.             /*//Printing Inorder
  311.             System.out.print("InOrder traversal:");
  312.             InOrder(root);
  313.             System.out.println();
  314.  
  315.             //printing postorder
  316.             System.out.print("PostOrder traversal:");
  317.             PostOrder(root);
  318.             System.out.println();*/
  319.             //Printing all traversals iteratively
  320.             //Printing PreOrder
  321.           /* System.out.print("PreOrder traversal:");
  322.             IterativePreOrder(root);
  323.             System.out.println();
  324. */
  325.  
  326.            /* //Printing Inorder
  327.             System.out.print("InOrder traversal:");
  328.             IterativeInOrder(root);
  329.             System.out.println();
  330.  
  331.             //printing postorder
  332.             System.out.print("PostOrder traversal:");
  333.             IterativePostOrder(root);
  334.             System.out.println();
  335. */
  336.  
  337.  
  338.  
  339.  
  340.  
  341.     }
  342. }
  343.  
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
PreOrder traversal:1 2 3 4 5
https://ideone.com/oac3Kj
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!