@@ -0,0 +1,2405 @@
+package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;%0A%0Aimport com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;%0Aimport com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;%0A%0A/**%0A * Created by sundas on 6/10/2018.%0A */%0Apublic class InsertANodeInABST %7B%0A%0A  /*%0A  Insert a node in a binary search tree%0A   */%0A%0A  /**%0A   *%0A   * @param root%0A   */%0A   public static void insertIntoBST(BinaryTreeNode root,int key,BinaryTreeNode parent,boolean leftChild)%7B%0A     /*%0A     Essentially find an empty spot and insert it , fullfiling the BST criteria.%0A      */%0A     if(root == null)%7B%0A       BinaryTreeNode node = new BinaryTreeNode();%0A       node.data = key;%0A       /*%0A       We need to know the direction%0A        */%0A       if(parent != null)%7B%0A         if(leftChild)%7B%0A           parent.left = node;%0A         %7D%0A         else%7B%0A           parent.right = node;%0A         %7D%0A       %7D%0A       return;%0A     %7D%0A     if(root.data == key)%7B%0A       return;%0A     %7D%0A     /*%0A     Go left%0A      */%0A     if(key %3C root.data)%7B%0A       insertIntoBST(root.left,key,root,true);%0A     %7D%0A     /*%0A     Go right%0A      */%0A     else%7B%0A       insertIntoBST(root.right,key,root,false);%0A     %7D%0A   %7D%0A%0A  /**%0A   *%0A   * @param args%0A   */%0A  public static void main(String%5B%5D args) %7B%0A    BinaryTreeNode root = TreeUtils.createBST();%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22############################%22);%0A    insertIntoBST(root, 12, null, false);%0A    System.out.println(%22Inserting 12%22);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22############################%22);%0A    System.out.println(%22Inorder traversal%22);%0A    TreeUtils.inorder(root);%0A    insertIntoBST(root, 2, null, false);%0A    System.out.println(%22Inserting 12%22);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22############################%22);%0A    System.out.println(%22Inorder traversal%22);%0A    TreeUtils.inorder(root);%0A    insertIntoBST(root, 8, null, false);%0A    System.out.println(%22Inserting 8%22);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22############################%22);%0A    System.out.println(%22Inorder traversal%22);%0A    TreeUtils.inorder(root);%0A    insertIntoBST(root, 1, null, false);%0A    System.out.println(%22Inserting 1%22);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22############################%22);%0A    System.out.println(%22Inorder traversal%22);%0A    TreeUtils.inorder(root);%0A  %7D%0A%0A%7D%0A

Insert into BST recursive , O(N) worst case , O(logn) for balanced BST.