Binary Trees - I

The tree data structure is a collection of nodes that are arranged in a hierarchical order. The topmost node is called the root node while the rest below are called child nodes.

Data in a tree is not stored in sequential manner instead they are arranged on multiple levels. Hence tree is a non-linear data structure.

Representation of Binary Tree

public class BinaryTree {
     class Node {
           int data;
           Node left;
           Node right;

           public Node(int data){
                this.data = data;
                left = null;
                right = null;
           }
     }
}

Binary Tree Traversals

Pre-Order Traversal

public class BinaryTree {
    class Node{
           int data;
           Node left;
           Node right;

           public Node(int data){
                this.data = data;
                left = null;
                right = null;
           }
    }

    Node root = null;

    private Node insertNode(Node root, int data){
          if(root == null){
              return new Node(data);
          }

          if(root != null){
                 if(data < root.data){
                        root.left = insertNode(root.left, data);
                 } else if(data > root.data){
                        root.right = insertNode(root.right, data);
                 }
          }

          return root;
    }


    public void insert(int data){
          root = insertNode(root, data);
    }


   private void PreOrder(Node root, List<Integer> arr){
          if(root == null){
               return arr;
          }

          arr.add(root.data);
          PreOrder(root.left, arr);
          PreOrder(root.right, arr);
   }


   public List<Integer> preorder(){
         List<Integer> arr = new ArrayList<>();
         PreOrder(root, arr);
         return arr;
   }

   public static void main(String[], args){
          BinaryTree tree = new BinaryTree();

          tree.insert(4);
          tree.insert(10);
          tree.insert(15);
          tree.insert(5);
          tree.insert(20);
          tree.insert(1);

          List<Integer> arr = tree.preorder();
          System.out.println(arr);
   }
}

In-Order Traversal

public class BinaryTree{
     class Node {
          int data;
          Node left;
          Node right;

          public Node(int data){
                this.data = data;
                left = null;
                right = null;
          }
     }

     Node root = null;

    private Node insertNode(Node root, int data){
          if(root == null){
               return new Node(data);
          }

          if(root != null){
               if(data < root.data){
                    root.left = insertNode(root.left, data);
               }else if(data > root.data){
                    root.right = insertNode(root.right, data);
               }
          }
          return root;
    }

    public void insert(int data){
          root = insertNode(root, data);
    }

    private void InOrder(Node root, List<Integer> arr){
          if(root != null){
              InOrder(root.left, arr);
              arr.add(root.data);
              InOrder(root.right, arr);
          }
    }


   public List<Integer> inorder(){
          List<Integer> arr = new ArrayList<>();
          InOrder(root, arr);
          return arr;
   }

   public static void main(String[], args){
          BinaryTree tree = new BinaryTree();

          tree.insert(4);
          tree.insert(10);
          tree.insert(15);
          tree.insert(5);
          tree.insert(20);
          tree.insert(1);

          List<Integer> arr = tree.inorder();
          System.out.println(arr);
   }
}

Post-Order Traversal

public class BinaryTree {
     class Node{
          int data;
          Node left;
          Node right;

          public Node(int data){
               this.data = data;
               left = null;
               right = null;
          }
     }

     Node root = null;

     private Node insertNode(Node root, int data){
           if(root == null){
                return new Node(data);
           }

          if(root != null){
                if(data < root.data){
                      root.left = insertNode(root.left, data);
                } else if(data > root.data){
                      root.right = insertNode(root.right, data);
                }
          }

          return root;
     }

    public void insert(int data){
          root = insertNode(root, data);
    }

   private void PostOrder(Node root, List<Integer> arr){
          if(root != null){
                PostOrder(root.left, arr);
                PostOrder(root.right, arr);
                arr.add(root.data);
          }
   }

  public List<Integer> postorder(){
         List<Integer> arr = new ArrayList<>();
         PostOrder(root, arr);
         return arr;
  }

  public static void main(String[], args){
         BinaryTree tree = new BinaryTree();

         tree.insert(4);
         tree.insert(10);
         tree.insert(15);
         tree.insert(5);
         tree.insert(20);
         tree.insert(1);

         List<Integer> list = tree.postorder();
         System.out.print(list);
  }
}

Level Order Traversal

public class BinaryTree{
     class Node{
          int data;
          Node left;
          Node right;

          public Node(int data){
                this.data = data;
                left = null;
                right = null;
          }
     }

     Node root = null;

     private Node insertNode(Node root, int data){
           if(root == null){
                return new Node(data);
           }

           if(root != null){
                if(data < root.data){
                      root.left = insertNode(root.left, data);
                } else if(data > root.data){
                      root.right = insertNode(root.right, data);
                }
           }
           return root;
     }

     public void insert(int data){
           root = insertNode(root, data);
     }

     public List<List<Integer>> LevelOrder(Node root){
            List<List<Integer>> ans = new ArrayList<>();

            if(root == null){
                 return ans;
            }

            Queue<Node> queue = new LinkedList<>();
            queue.add(root);

            while(!queue.isEmpty()){
                  int size = queue.size();
                  List<Integer> level = new ArrayList<>();

                  for(int i = 0; i < size; i++){
                          Node current = queue.poll();
                          level.add(current.data);

                          if(current.left != null){
                                 queue.add(current.left);
                          }
                          if(current.right != null){
                                  queue.add(current.right);
                          }
                  }
                  ans.add(level);
            }
            return ans;
     } 

     public List<List<Integer>> levelorder(){
            return LevelOrder(root);
     }

     public static void main(String[], args){
            BinaryTree tree = new BinaryTree();

            tree.insert(10);
            tree.insert(6);
            tree.insert(15);
            tree.insert(3);
            tree.insert(8);
            tree.insert(20);

            List<List<Integer>> result = tree.levelorder();

            for (List<Integer> level : result) {
                  System.out.println(level);
            }
     }
}

Post-Order Traversal Using Two Stacks

public class BinaryTree {
    class Node{
        int data;
        Node left;
        Node right;

        public Node(int data){
            this.data = data;
            left = null;
            right = null;
        }
    }

    Node root = null;


    private Node insertNode(Node root, int data){
        if(root == null){
            return new Node(data);
        }

        if(root != null){
            if(data < root.data){
                root.left = insertNode(root.left, data);
            } else if (data > root.data) {
                root.right = insertNode(root.right, data);
            }
        }
        return root;
    }


    public void insert(int data){
        root = insertNode(root, data);
    }


    private List<Integer> postorder(Node root){
        List<Integer> postOrder = new ArrayList<>();

        if(root == null){
            return postOrder;
        }

        Stack<Node> st1 = new Stack<>();
        Stack<Node> st2 = new Stack<>();

        st1.push(root);

        while(!st1.isEmpty()){
            root = st1.pop();
            st2.push(root);

            if(root.left != null){
                st1.push(root.left);
            }
            if(root.right != null){
                st1.push(root.right);
            }
        }


        while(!st2.isEmpty()){
            postOrder.add(st2.pop().data);
        }

        return postOrder;

    }

    public List<Integer> postOrder(){
        return postorder(root);
    }


    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(10);
        tree.insert(6);
        tree.insert(15);
        tree.insert(3);
        tree.insert(8);
        tree.insert(20);

        List<Integer> arr = tree.postOrder();

        System.out.print(arr + " ");
    }

}