fork(3) download
copy 
  1. import java.util.*;
  2.  
  3. class BinaryTreeUtil {
  4.  
  5.     public Node root;
  6.     static class Node {
  7.         int data;
  8.         Node left;
  9.         Node right;
  10.  
  11.         Node(int data) {
  12.             this.data = data;
  13.         }
  14.     }
  15.  
  16.     public static void main(String[] args) {
  17.         BinaryTreeUtil sizeUtil = new BinaryTreeUtil();
  18.         sizeUtil.root = sizeUtil.getSampleTree();
  19.  
  20.         System.out.println("Size of the tree is " + sizeUtil.getSize(sizeUtil.root));
  21.  
  22.         letsDo("Inorder Traversal");
  23.         sizeUtil.inorderTraversal(sizeUtil.root);
  24.         newLine();
  25.  
  26.         letsDo("Level Order Traversal in Reverse Order using Stack and Queue");
  27.         sizeUtil.levelOrderTraversalInReverseOrderUsingStackAndQueue(sizeUtil.root);
  28.         newLine();
  29.  
  30.     }
  31.  
  32.     public static void letsDo(String task) {
  33.         System.out.println("=============" + task + "==================");
  34.     }
  35.  
  36.     public static void newLine() {
  37.         System.out.println();
  38.     }
  39.  
  40.     public Node getSampleTree() {
  41.         Node root = new Node(1);
  42.  
  43.         root.left = new Node(2);
  44.         root.left.left = new Node(4);
  45.         root.left.right = new Node(5);
  46.         root.right = new Node(3);
  47.  
  48.  
  49.         return root;
  50.     }
  51.  
  52.     public int getSize(Node root) {
  53.         if (root == null)
  54.             return 0;
  55.         return getSize(root.left) + 1 + getSize(root.right);
  56.     }
  57.  
  58.     public void inorderTraversal(Node root) {
  59.         if (root == null)
  60.             return;
  61.         inorderTraversal(root.left);
  62.         System.out.print(root.data + ",");
  63.         inorderTraversal(root.right);
  64.     }
  65.  
  66.     public void levelOrderTraversalInReverseOrderUsingStackAndQueue(Node root) {
  67.         Stack<Node> stack = new Stack<>();
  68.         Queue<Node> queue = new LinkedList<>();
  69.         Node temp;
  70.  
  71.         queue.add(root);
  72.         while (!queue.isEmpty()) {
  73.             temp = queue.poll();
  74.             stack.push(temp);
  75.             // Enqueue first Right then left because we are storing the end result in stack which is actually LIFO
  76.             if (temp.right != null) {
  77.                 queue.add(temp.right);
  78.             }
  79.             if (temp.left != null) {
  80.                 queue.add(temp.left);
  81.             }
  82.         }
  83.         while (!stack.isEmpty()) {
  84.             temp = stack.pop();
  85.  
  86.             if (temp == null) {
  87.                 System.out.println();
  88.                 continue;
  89.             }
  90.             System.out.print(temp.data + "\t");
  91.         }
  92.     }
  93. }
  94.  
Success #stdin #stdout 0.04s 4575232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Size of the tree is 5
=============Inorder Traversal==================
4,2,5,1,3,
=============Level Order Traversal in Reverse Order using Stack and Queue==================
4	5	2	3	1
https://ideone.com/CSShmp
language:
Java (HotSpot 12)
created:
8 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!