Binary Trees - II

Height 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;
           }
     }

     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 int MaxDepth(Node root){
           if(root == null){
                return 0;
           }

           Queue<Node> queue = new LinkedList<>();
           int level = 0;

           queue.add(root);

           while(!queue.isEmpty()){
                int size = queue.size();

                for(int i = 0; i < size; i++){
                       Node curr = queue.poll();

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

     public int height(){
           return MaxDepth(root);
     }

     public static void main(String[] args){
           BinaryTree tree = new BinaryTree();
           tree.insert(5);
           tree.insert(4);
           tree.insert(9);
           tree.insert(8);
           tree.insert(10);
           tree.insert(11);
           System.out.println(tree.height());
     }

}

Diameter 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;
           }
      }

      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);
      }

      int diameter = 0;

      private int getHeight(Node root){
           if(root == null){
                return 0;
           }

           int leftHeight = getHeight(root.left);
           int rightHeight = getHeight(root.right);

           diameter = 1 + Math.max(diameter, leftHeight + rightHeight);
           return 1 + Math.max(leftHeight, rightHeight);
      }

      public int height(){
          getHeight(root);
          return diameter;
      }

      public static void main(String[] args){
           BinaryTree tree = new BinaryTree();
           tree.insert(5);
           tree.insert(4);
           tree.insert(9);
           tree.insert(10);
           tree.insert(11);
           System.out.println(tree.height());
      }
}

Check If Two Trees Are Identical

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 boolean isIdentical(Node node1, Node node2){
            if(node1 == null && node2 == null){
                  return true;
            }

            if(node1 == null || node2 == null){
                   return false;
            }

            return((node1.data == node2.data) && isIdentical(node1.left, node2.left) && isIdentical(node1.right, node2.right));
      }

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


            tree1.insert(5);
            tree1.insert(4);
            tree1.insert(9);
            tree1.insert(10);
            tree1.insert(11);


            tree2.insert(5);
            tree2.insert(4);
            tree2.insert(9);
            tree2.insert(10);
            tree2.insert(11);

             System.out.println(tree1.isIdentical(tree1.root, tree2.root));
      }
}

Symmetrical Binary Tree

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 boolean isSymmetric(Node root1, Node root2){
        if(root1 == null || root2 == null){
             return root1 == root2;
        }

        return((root1.data == root2.data) && isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left));
    }

    public boolean symmetric(){
          return isSymmetric(root, root);
    }

    public static void main(String[] args){
          BinaryTree tree = new BinaryTree();
          tree.insert(5);
          tree.insert(4);
          tree.insert(9);
          tree.insert(10);
          tree.insert(11);
          System.out.println(tree.symmetric());
    }
}

Balanced Binary Tree

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 int BalancedHeight(Node root){
           if(root == null){
               return 0;
           }

           int leftHeight = BalancedHeight(root.left);
           if(leftHeight == -1){
                return -1;
           }

           int rightHeight = BalancedHeight(root.right);
           if(rightHeight == -1){
                return -1;
           }

           if(Math.abs(rightHeight - leftHeight) > 1){
                 return -1;
           }

           return Math.max(leftHeight, rightHeight) + 1;
     }

     public static void main(String[] args){
           BinaryTree tree = new BinaryTree();
           tree.insert(5);
           tree.insert(4);
           tree.insert(9);
           tree.insert(10);
           tree.insert(11);
           System.out.println(tree.BalancedHeight(tree.root));
     }
}

Top View 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;
          }
     }

     Node root = null;


     class QueueNode{
            Node node;
            int pos;

            public QueueNode(Node node, int pos){
                  this.node = node;
                  this.pos = pos; 
            }
     }

     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<Integer> topView(Node root){
           List<Integer> ans = new ArrayList<>();

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

           Queue<QueueNode> queue = new LinkedList<>();
           Map<Integer, Integer> mpp = new HashMap<>();

           queue.add(new QueueNode(root, 0));

           while(!queue.isEmpty()){
                QueueNode curr = queue.poll();

                Node currNode = curr.node;
                int pos = curr.pos;

                if(!mpp.containsKey(pos)){
                      mpp.put(pos, currNode.data);
                }

                if(currNode.left != null){
                      queue.add(new QueueNode(currNode.left, pos - 1));
                }
                if(currNode.right != null){
                      queue.add(new QueueNode(currNode.right, pos + 1));
                }
           }

           ans.addAll(mpp.values());
           return ans;
     }

     public static void main(String[] args){
           BinaryTree tree = new BinaryTree();
           tree.insert(5);
           tree.insert(4);
           tree.insert(9);
           tree.insert(8);
           tree.insert(10);
           tree.insert(11);
           System.out.println(tree.topView(tree.root));
     }
}

Bottom View 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;
          }
     }

     Node root = null;


     class QueueNode{
            Node node;
            int pos;

            public QueueNode(Node node, int pos){
                  this.node = node;
                  this.pos = pos; 
            }
     }

     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<Integer> topView(Node root){
           List<Integer> ans = new ArrayList<>();

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

           Queue<QueueNode> queue = new LinkedList<>();
           Map<Integer, Integer> mpp = new HashMap<>();

           queue.add(new QueueNode(root, 0));

           while(!queue.isEmpty()){
                QueueNode curr = queue.poll();

                Node currNode = curr.node;
                int pos = curr.pos;

                mpp.put(pos, currNode.data);

                if(currNode.left != null){
                      queue.add(new QueueNode(currNode.left, pos - 1));
                }
                if(currNode.right != null){
                      queue.add(new QueueNode(currNode.right, pos + 1));
                }
           }

           ans.addAll(mpp.values());
           return ans;
     }

     public static void main(String[] args){
           BinaryTree tree = new BinaryTree();
           tree.insert(5);
           tree.insert(4);
           tree.insert(9);
           tree.insert(8);
           tree.insert(10);
           tree.insert(11);
           System.out.println(tree.topView(tree.root));
     }
}

Boundary Traversal Of Binary Tree

public class BoundaryTraversal {
    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 boolean isLeaf(Node root){
        if(root.left == null && root.right == null){
            return true;
        }
        return false;
    }

    private void addLeftBoundary(Node root, List<Integer> res){
        Node curr = root.left;

        while(curr != null){
            if(!isLeaf(curr)){
                res.add(curr.data);
            }

            if(curr.left != null){
                curr = curr.left;
            }else{
                curr = curr.right;
            }
        }
    }

    private void addRightBoundary(Node root, List<Integer> res){
        Node curr = root.right;
        List<Integer> temp = new ArrayList<>();

        while(curr != null){
            if(!isLeaf(curr)){
                temp.add(curr.data);
            }

            if(curr.right != null){
                curr = curr.right;
            }else{
                curr = curr.left;
            }
        }

        for (int i = temp.size() - 1; i >= 0 ; --i) {
            res.add(temp.get(i));
        }
    }

    private void addLeaves(Node root, List<Integer> res){
        if(isLeaf(root)){
            res.add(root.data);
        }

        if(root.left != null){
            addLeaves(root.left, res);
        }
        if(root.right != null){
            addLeaves(root.right, res);
        }

    }

    public List<Integer> printBoundary(Node root){
        List<Integer> res = new ArrayList<>();

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

        if(!isLeaf(root)){
            res.add(root.data);
        }

        addLeftBoundary(root,res);
        addLeaves(root,res);
        addRightBoundary(root,res);

        return res;
    }

    public List<Integer> print(){
        return printBoundary(root);
    }


    public static void main(String[] args) {
        BoundaryTraversal tree = new BoundaryTraversal();
        tree.insert(5);
        tree.insert(4);
        tree.insert(9);
        tree.insert(10);
        tree.insert(11);

        System.out.println(tree.print());
    }
}