package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;

import com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;
import com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;

/**
 * Created by sundas on 6/10/2018.
 */
public class InsertANodeInABST {

  /*
  Insert a node in a binary search tree
   */

  /**
   *
   * @param root
   */
   public static void insertIntoBST(BinaryTreeNode root,int key,BinaryTreeNode parent,boolean leftChild){
     /*
     Essentially find an empty spot and insert it , fullfiling the BST criteria.
      */
     if(root == null){
       BinaryTreeNode node = new BinaryTreeNode();
       node.data = key;
       /*
       We need to know the direction
        */
       if(parent != null){
         if(leftChild){
           parent.left = node;
         }
         else{
           parent.right = node;
         }
       }
       return;
     }
     if(root.data == key){
       return;
     }
     /*
     Go left
      */
     if(key < root.data){
       insertIntoBST(root.left,key,root,true);
     }
     /*
     Go right
      */
     else{
       insertIntoBST(root.right,key,root,false);
     }
   }

  /**
   *
   * @param args
   */
  public static void main(String[] args) {
    BinaryTreeNode root = TreeUtils.createBST();
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("############################");
    insertIntoBST(root, 12, null, false);
    System.out.println("Inserting 12");
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("############################");
    System.out.println("Inorder traversal");
    TreeUtils.inorder(root);
    insertIntoBST(root, 2, null, false);
    System.out.println("Inserting 12");
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("############################");
    System.out.println("Inorder traversal");
    TreeUtils.inorder(root);
    insertIntoBST(root, 8, null, false);
    System.out.println("Inserting 8");
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("############################");
    System.out.println("Inorder traversal");
    TreeUtils.inorder(root);
    insertIntoBST(root, 1, null, false);
    System.out.println("Inserting 1");
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("############################");
    System.out.println("Inorder traversal");
    TreeUtils.inorder(root);
  }

}

@@ -312,16 +312,921 @@
 %0A   */%0A%0A
+  /**%0A   *%0A   * @param root%0A   * @param key%0A   * @return%0A   */%0A  public static BinaryTreeNode insertIntoBSTIterative(BinaryTreeNode root,int key)%7B%0A    BinaryTreeNode node = new BinaryTreeNode();%0A    node.data = key;%0A    if(root == null)%7B%0A      return node;%0A    %7D%0A    BinaryTreeNode current = root;%0A    boolean left = false;%0A    BinaryTreeNode parent = null;%0A    /*%0A    Find slot for insertion%0A     */%0A    while(current != null)%7B%0A      if(key == current.data)%7B%0A        return root;%0A      %7D%0A      if(key %3C current.data)%7B%0A        parent = current;%0A        current = current.left;%0A        left = true;%0A      %7D%0A      else%7B%0A        parent = current;%0A        current = current.right;%0A        left = false;%0A      %7D%0A    %7D%0A    /*%0A    Found insertion point%0A     */%0A    if(parent != null) %7B%0A      if (left) %7B%0A        parent.left = node;%0A      %7D else %7B%0A        parent.right = node;%0A      %7D%0A    %7D%0A    return root;%0A  %7D%0A%0A
   /**%0A  
@@ -3296,15 +3296,960 @@
 (root);%0A
+    System.out.println(%22################## Iterative ##########%22);%0A    root = TreeUtils.createBST();%0A    System.out.println(%22Insert 12%22);%0A    root = insertIntoBSTIterative(root, 12);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22#####################%22);%0A    TreeUtils.inorder(root);%0A    //root = TreeUtils.createBST();%0A    System.out.println(%22Insert 2%22);%0A    root = insertIntoBSTIterative(root, 2);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22#####################%22);%0A    TreeUtils.inorder(root);%0A    System.out.println(%22Insert 1%22);%0A    root = insertIntoBSTIterative(root, 1);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22#####################%22);%0A    TreeUtils.inorder(root);%0A    System.out.println(%22Insert 1%22);%0A    root = insertIntoBSTIterative(root, 100);%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22#####################%22);%0A    TreeUtils.inorder(root);%0A
   %7D%0A%0A%7D%0A

Insert into BST iterative.