Java Algorithms Trees

• A tree will have a root node on its top and it has child and child have child. 
• Node with out child are called leaf.
• A Binary Tree contains nodes with two children always.Each node has left node and right node. 
• Binary search tree is a binary tree having specific ordering. Here always left node contains lesser and right node contains higher values. This ordering will make finding a node very fast. 
  
• Insertion: There are two types of insertion are there Balanced and Unbalanced 
  
• Balanced Insertion
• Inserts on next free child based on left right order and time complexity will be lesser here.
• Unbalanced Insertion
•  insert go deep of list and time complexity is higher. 
•  Traversing 
  
• In-order Traverse
  
•  Visit left node first then root node and then right node
•  Pre-order
• Visit root node first then left node and right node.
• Post-Order 
• Visit left node first then right node and last root node. 
•  Code approach 
• For Insert 
• Compare value with root value.
•  If value lesser or equal to root value then go to left child node. Put value in child node if child node is null.
• If child node not null then pass the value to insert method of child. 
• If value is greater than root node value then do the same with right node. 
• For Contains 
• Check node value equals to value. 
• If equals then return true. 
• Else if value lesser than root value then go to left. If left node is null return false else call contains method of left node.
• Else if value greater than root node value then go to right node and do the same there.

public class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } public void insert(int value) { if (value <= data) { // inserting if left node is free if (left == null) { left = new Node(value); } else { // forward to next node if left node aleady occupied. left.insert(value); } } else { if (right == null) { right = new Node(value); } else { right.insert(value); } } } public boolean contains(int value) { if (data == value) { return true; } else if (value < data) { if (left == null) { return false; } else { left.contains(value); } } else { if (right == null) { return false; } else { right.contains(value); } } return false; } public void inOrderPrinting() { if (left != null) { left.inOrderPrinting(); } System.out.println(data); if (right != null) { right.inOrderPrinting(); } } }

Reference Link https://www.youtube.com/watch?v=oSWTXtMglKE