Best unstable in-place sort : Heap Sort

Big O notation and visualization

Most of time algorithm performance is measured by time complexity . Space complexity is also important but it is compromised most of time . If space required is not much compared to modern hardware then it can be ignored .

In computer science when there are two or more ways or algorithms to solve the problem we need to choose best one which completes in less time .

Practical way is ,for same hardware ,  for same size , run algorithms , use e.g. System.nanoTime()  to measure time  then compare them together .  We might need to run experiment for all possible sizes .
Instead of writing all possible approaches and measuring time for actual scenarios is time consuming.

Is there any other way for such comparison  of algorithms ?
Yes there is which uses asymptotic notation called Big_O_notation .

Big O notation denoted maximum time taken by algorithm for given size of problem .
It is asymptotic (tangent at infinity) upper bound.

 f(n) = O(g(n)) and if there exists constant c and  n0 such that
f(n) <= c*g(n) for n >= n0

 f(n) ,  g(n) are functions over non-negative integers .

Big O notation is used for worst case analysis of algorithms .

Instead of calculating actual time , it measures growth of time with growth of the problem size .

Every time size of problem increases , time is bound to increase .

Example :  To find maximum element in array using scanning is O(n) means as size of array increases we will need more time to find the maximum element . Say maximum element is located at end . If array size is of 10 then it takes 10 mSecs to find the element . If array size if 10 million then time requires could be 100 secs which is 1.5 min . if array size is of 1 billion then it will be 1500 min which is too large .

If say 1 Billion array is circularly sorted and we use binary search for the problem which is O(log(n)) then time required will be 20 mSec which is very fast .

So if we have efficient algorithm then on even commodity machine we can give fast outputs.

To calculate  "Big O notation" we need to consider only higher order terms .

Example :

n^2 + 4n+3 is O(n^2)

nlog2(n) + 10n + 1 is O(nlog2(n))


Asymptotic running time by comparison n --> infinity

1 < log2(n) < n < nlog2(n) < n^2 < 2^n


Theta (asymptotically tight bound ) , Ohh (upper bound ) and Omega (lower bound) notation differences

Figure (a) : Theta notation consider theta function sandwiching actual function  by upper and lower bounds
Figure (b) : Oh notation consider it as equal or upper bound or worst case
Figure (c) : Omega notation is function which confines equal or lower bounds. consider it as best case where time required is less.

little Ohh notation is strictly above the function .
little Omega is strictly below the function .

e.g.  Insertion sort for already sorted array Theta is between n^2 and n so big ohh is n^2 and omega is n only.

Most of time you will check big ohh notation because we are interested in worst case performance .

Graph of T(n) = O(g(n))

 From left to right (Y axis to X)
O(2^n), O(n^2) , O(n*log2(n)) ,O(n) , O(sqrt(n)) ,  O(log2(n))

Slowest growth of time for given input is O(log2(n)) .

Legends

Y - time in secs to execute the algorithm
X - number of items as input to algorithm

Selection of algorithm for sorting

Sorting is the fundamental operation in computer science .

Choice of sorting algorithm depends on

1. Number of items to be sorted
2. Number of items already somewhat sorted
3. Possible restrictions on item values like comparing operation
4. Computer architecture like number of CPUs , IO speed , main memory , disk space
5. Nature of computing multi-threaded or parallel distributed
6. Stability of sort
7. Is there need for extra space or  in-place sort ?
8. Is multi-algorithm sort optimization strategy needed ? example - if size of merge sort say below 30-40 then use insertion sort else use merge sort during divide phase of the algorithm .
9. Ease of implementation.  example - in-place merge sort implementation is theoretically possible but extremely difficult for practical purposes .

 Comparison of algorithms
 




In practice best algorithm is heap sort because it is in-place and running time is on par with merge sort .
But biggest disadvantage of heap sort is it is not stable sort .

So when there is no requirement of stability use heap sort else use merge sort in combination with insertion sort (for size of 30-40 ) .

Search element in circularly sorted array .(Java Code)

Problem :  Search index of element in circularly sorted array . Elements are not repeated.

Observations :

Whenever array is sorted always look out for usage of binary search for best worst performance .

Scanning array 

Iterate over array and just look for element once we get break the loop.

Time complexity , T(n) = n


Tweaked binary search 

Sorted array -->  1,2,3,4,5,6,7,8,9,10,11

intput -->

After one rotation --> 11,1,2,3,4,5,6,7,8,9,10

if we are searching for 9
Output --> 8


For mid pivot ( ( high+low )/2) of 5 right half is sorted . while left is not sorted .
So for any rotation one half will be sorted and other will not be .
Based on this fact we need to direct binary search to the part of circular array .


Time complexity ,  T(n) = log2(n)


Java Code 

package com.salpe.sort;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 @Test
 public  void testSuccess() {

  int[] arr = new int[] {1,2,3,4,5,6,7,8,9,10,11};

  Assert.assertEquals(4, searchCircularArray(arr, 5));

  arr = new int[] {11,1,2,3,4,5,6,7,8,9,10};

  Assert.assertEquals(5, searchCircularArray(arr, 5));

  arr = new int[] {10,11,1,2,3,4,5,6,6,7,8,9};

  Assert.assertEquals(6, searchCircularArray(arr, 5));

 }
 
 /**
  * <p>
  * mid always divides array between one sorted and one unsorted sub arrays.
  * 
  * <p>
  * array rotated by 2 --> 11,10,1,2,3,4,5,6,7,8,9
  * <p>
  * mid element is 4 left of 4 is not sorted , right of 4 is sorted
  * 
  * <p>
  * If it is sorted then check lo and hi to check value in it else go to
  * other unsorted half.
  * <p>
  * 
  * T(n) = log2(n)
  * 
  * @param arr
  * @param val
  * @return
  */
 public static int searchCircularArray(int[] arr, int val) {

  int lo = 0;
  int hi = arr.length - 1;

  while (lo <= hi) {

   // find mid pivot
   int mid = (lo + hi) / 2;

   // if mid matches game over
   if (arr[mid] == val) {

    return mid;

   }
   // right array sorted
   else if (arr[mid] < arr[hi]) {

    // check value contains in sorted right
    if (val > arr[mid] && val <= arr[hi]) {

     lo = mid + 1;

    } else {

     hi = mid - 1;
    }

   }
   // left array sorted
   else {

    // check value contains in sorted left
    if (val < arr[mid] && val >= arr[lo]) {

     hi = mid - 1;

    } else {

     lo = mid + 1;
    }
   }

  }

  // oops no match found
  return -1;

 }

}

Tracing a recursive function .

Observations :



Problem :  Find the values of n printed to console .

public static void function123(int n){
  
   if(n<=0){
    
    return;
   }
  
   System.out.println(n);
   
   function123(n-2);
   function123(n-3);
 
   
   System.out.println(n);
  
 }

Solution :


Problem :  Find the values of n printed to console .

static int fib( int n )
 {
    if ( n == 0 )  // base case 1
      return 1;
    else if ( n == 1 )  // base case 2
      return 2;
    else
      {
         int resultA = fib( n - 1 ); // "A"
         int resultB = fib( n - 2 ); // "B"
         
         System.out.println(resultA+resultB);
         
         return resultA + resultB;
      }
 }

Solution :



Problem :  Trace the path of recursion

public int searchWithR(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   return mid;

  } else if (value < arr[mid]) {

   // change value of high , one position left of mid
   return searchWithR(arr, value, lo, mid - 1);

  } else {

   // change value of low , one position right of mid
   return searchWithR(arr, value, mid + 1, hi);
  }

 }

Binary search on sorted array (Java Code)

Problem - What is efficient way to search a sorted array .

Observations :

 For searching an element in the array strategy depends on nature of data in array .

1. If array is not sorted there is no other way than sequential scan of the array .
2. If array is sorted but length is not known then jump search ( jump with constant size or Fibonacci number or exponential factor ) could be used to improve sequential scan .
3. If array is sorted and length is known then binary search is best way to do the search .

Binary is search is well known divide and conquer algorithm .
It can be implemented using recursion or without recursion using stack .

Algorithm Complexity :  worst case  Ω(log2(n)) , average case O(log2(n)) , best case O(1) .


Sequential Search for sorted array 

To search  7th place we have to traverse to 7 places.  which proves complexity  O(n) .

Binary Search for sorted array 

To search 7th place ,  we have to traverse 3 places . which proves complexity O(log2(n)).


Java Code 

package com.salpe.arrays;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 @Test
 public void testSuccess() {

  int[] arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };

  int result1 = searchWithR(arr, 7, 0, arr.length - 1);

  Assert.assertEquals(result1, 7);

  int result2 = searchWithoutR(arr, 7, 0, arr.length - 1);

  Assert.assertEquals(result2, 7);

 }

 public int searchWithR(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   return mid;

  } else if (value < arr[mid]) {

   // change value of high , one position left of mid
   return searchWithR(arr, value, lo, mid - 1);

  } else {

   // change value of low , one position right of mid
   return searchWithR(arr, value, mid + 1, hi);
  }

 }

 public int searchWithoutR(int[] arr, int value, int lo, int hi) {

  // condition to check less than or equal* is very important
  while (lo <= hi) {

   int mid = (lo + hi) / 2;

   if (arr[mid] == value) {

    return mid;

   } else if (value < arr[mid]) {

    // change value of high , one position left of mid
    hi = mid - 1;

   } else {

    // change value of low , one position right of mid
    lo = mid + 1;
   }

  }

  // return is case no result found
  return -1;
 }

}

Binary Search Tree : Check whether given binary tree is binary search tree or not .

Problem :

Check whether given binary tree is binary search tree or not.


Observation :

Binary Tree - tree with maximum two leaves .
Binary search tree (BST) - tree with maximum two leaves such that  (left < root < right ) leaf.

For binary tree to be as binary search tree properties  are

1. left sub-tree must be less than root .
2. right sub-tree must be greater than root.
3. Means value of root must lie between limits of left and right values .

Or

1. If we do in-order traversal of the tree it must give values sorted in ascending order

Algorithm Type : Recursion


Java code using above two properties

package com.salpe.tree;

import java.util.logging.Logger;

import org.junit.Assert;
import org.junit.Test;

/**
 * Check whether given binary tree is binary search tree or not 
 *
 */
public class BSTTest5 {

 private static final Logger s_logger = Logger.getLogger(BSTTest2.class.getName());

 /**
  * Binary tree pre-order list as 0,1,2,3,4,5,6
  */
 @Test
 public void testSuccess() {

  BST<Integer> bst = createSuccessTestData();

  boolean resultSubBSTChk = bst.isBSTUsingSubBSTChk();
  boolean resultInorderChk = bst.isBSTUsingInorderChk();

  s_logger.info("Using subSBTChk: " + Boolean.toString(resultSubBSTChk));
  s_logger.info("using InorderChk:  " + Boolean.toString(resultInorderChk));
  Assert.assertTrue(resultSubBSTChk);
  Assert.assertTrue(resultInorderChk);

 }

 /**
  * tests when binary search tree is degraded to linked list
  */
 @Test
 public void testWorstCaseSuccess() {

  BST<Integer> bst = createSuccessWorstCaseTestData();

  boolean resultSubBSTChk = bst.isBSTUsingSubBSTChk();
  boolean resultInorderChk = bst.isBSTUsingInorderChk();

  s_logger.info("Using subSBTChk: " + Boolean.toString(resultSubBSTChk));
  s_logger.info("using InorderChk:  " + Boolean.toString(resultInorderChk));
  Assert.assertTrue(resultSubBSTChk);
  Assert.assertTrue(resultInorderChk);
 }

 @Test
 public void testFailure() {

  BST<Integer> bst = createFailureTestData();
  boolean resultSubBSTChk = bst.isBSTUsingSubBSTChk();
  boolean resultInorderChk = bst.isBSTUsingInorderChk();

  s_logger.info("Using subSBTChk: " + Boolean.toString(resultSubBSTChk));
  s_logger.info("using InorderChk:  " + Boolean.toString(resultInorderChk));
  Assert.assertFalse(resultSubBSTChk);
  Assert.assertFalse(resultInorderChk);

 }



 private BST<Integer> createSuccessTestData() {
  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);

  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);

  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);
  return bst;
 }

 /**
  * worst case is linked list for binary tree
  * 
  * @return
  */
 private BST<Integer> createSuccessWorstCaseTestData() {
  // create test data

  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, null, node06);

  BSTNode<Integer> node04 = new BSTNode<>(4, null, node05);

  BSTNode<Integer> node03 = new BSTNode<>(3, null, node04);

  BSTNode<Integer> node02 = new BSTNode<>(2, null, node03);

  BSTNode<Integer> node01 = new BSTNode<>(1, null, node02);

  BSTNode<Integer> node0 = new BSTNode<>(0, null, node01);

  // create BST
  BST<Integer> bst = new BST<>(node0);
  return bst;
 }

 private BST<Integer> createFailureTestData() {
  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);

  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  BSTNode<Integer> node06 = new BSTNode<>(-600, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);

  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);
  return bst;
 }

 /**
  * Binary Tree Node model
  *
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  T data;
  BSTNode<T> left;
  BSTNode<T> right;

  BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {

   this.data = data;
   this.left = left;
   this.right = right;

  }

  @Override
  public String toString() {
   return "BSTNode [data=" + data + "]";
  }

 }

 /**
  * Binary Tree Representation
  *
  * @param <T>
  */
 static class BST<T extends Comparable<T>> {

  BSTNode<T> root;

  public BST(BSTNode<T> root) {
   this.root = root;
  }

  boolean isBSTUsingSubBSTChk() {

   return isBSTUsingSubBSTChk0(root);
  }

  /**
   * @param root
   * @return whether binary tree is BST
   */
  private boolean isBSTUsingSubBSTChk0(BSTNode<T> root) {

   if (root == null) {

    return true;

   }

   if ((root.left != null && (root.data.compareTo(root.left.data) < 0))
     || ((root.right != null) && (root.data.compareTo(root.right.data) > 0))) {

    return false;
   }

   // left part is BST
   boolean isLeftBST = isBSTUsingSubBSTChk0(root.left);

   // right part is BST
   boolean isRightBST = isBSTUsingSubBSTChk0(root.right);

   // left , middle , right is BST if all are BST
   return isLeftBST && isRightBST;

  }

  boolean isBSTUsingInorderChk() {

   return isBSTUsingInorderChk0(root, null);
  }

  private boolean isBSTUsingInorderChk0(BSTNode<T> node, T prev) {

   if (node == null) {

    return true;
   }

   boolean leftPartInorder = isBSTUsingInorderChk0(node.left, prev);

   boolean isleftBeforeRight = (prev != null ? prev.compareTo(node.data) < 0 : true);

   boolean rightPartInorder = isBSTUsingInorderChk0(node.right, node.data);

   return leftPartInorder && isleftBeforeRight && rightPartInorder;

  }

 }
}

Iterate over Binary Search Tree (BST) - DepthFirst (preOrder, inOrder, postOrder ) , breadthFirst (Java Code)

Problem :

Traverse over binary search  tree.

Solution -

Lets take very simple tree with 2 as root and left as 1 and right as 2.

Depth First : Traverse through columns/vertical . For very big binary search tree such traversal could be time consuming .
Goes to farthest left node then traverse remaining and then go to farthest right node .

Pre-Order traversal  = 2,1,3
In-Order traversal =  1,2,3 (it is always sorted list in ascending order.)
Post-Order traversal = 1,3,2

Same logic will apply for any BST with any number of nodes .

Typically these are recursive functions otherwise stack is used to implement non-recursive functions.
It will be same logic for binary tree and graph .

Breath First :

Typically it is implemented using  queue .

Traverse through rows/horizontal  . For very big binary tree optimization could  be done like after 100th level ignore next levels etc .
Traverse one level distance away in each recursion .
It will be same logic for binary tree and graph .

level by level traversal = 2,1,3 or 2,3,1

Same logic will apply for any BST with any number of nodes .

package com.salpe.tree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.logging.Logger;

import org.junit.Test;

import com.salpe.tree.BSTUtils.BST.IteratorType;

/**
 * Binary tree could be traversed in two ways 
 * 1. Depth First
 *   a) pre-order
 *   b) in-order
 *   c) post-order
 * <p>
 * 2. Breadth First - level by level
 * </p>
 *
 */

public class BSTUtils {

 // logger 
 private static final Logger s_logger = Logger.getLogger(BSTUtils.class.getName());

 // Binary tree node model 
 static class BST<T extends Comparable<T>> {

  public enum IteratorType {

   PRE_ORDER, IN_ORDER, POST_ORDER,

   BREATH_FIRST;
  }

  private BSTNode<T> root;

  private int length;

  public void add(T data) {

   if (root == null) {

    root = new BSTNode<T>(data, null, null);
   } else {

    add0(root, data);

   }

  }

  /**
   * BST shape depends on order of insertion - not optimized for re-balancing 
   * @param node
   * @param data
   * @return added node
   */
  private BSTNode<T> add0(BSTNode<T> node, T data) {

   if (node == null) {

    length++;
    return new BSTNode<T>(data, null, null);
   }

   if (data.compareTo(node.id) < 0) {

    node.left = add0(node.left, data);

   } else if (data.compareTo(node.id) > 0) {

    node.right = add0(node.right, data);
   } else {

    return node;
   }

   return node;
  }

  /**
   * For searching binary tree must be binary search tree.
   * 
   * @param data
   * @return searched node
   */
  public BSTNode<T> search(T data) {

   BSTNode<T> start = root;

   while (start != null) {
    if (data.compareTo(start.id) < 0) {
     start = start.left;
    } else if (data.compareTo(start.id) > 0) {
     start = start.right;
    } else {
     return start;
    }
   }

   return null;
  }

  /**
   *  Iterator design pattern .
   *  But it is eager fetching so not true iterator design pattern 
   *  
   * @param type
   * @return Iterator
   */
  public Iterator<T> iterator(IteratorType type) {
   LinkedList<T> list = new LinkedList<>();
   switch (type) {
   case PRE_ORDER:
    preOrderTraversal(root, list);
    break;
   case IN_ORDER:
    inOrderTraversal(root, list);
    break;
   case POST_ORDER:
    postOrderTraversal(root, list);
    break;
   case BREATH_FIRST:
    breadthFirstTraveral(root, list);

   default:
    break;
   }

   return list.iterator();

  }

  /**
   * first visit left then current then right node.
   *  Could be converted in non-recursive function using stack 
   * @param node
   * @param list
   */
  private void inOrderTraversal(BSTNode<T> node, LinkedList<T> list) {

   if (node == null) {

    return;
   }

   inOrderTraversal(node.left, list);
   list.add(node.id);
   inOrderTraversal(node.right, list);
  }

  /**
   * first visit current then left and then right node.
   * Could be converted in non-recursive function using stack 
   * @param node
   * @param list
   */
  private void preOrderTraversal(BSTNode<T> node, LinkedList<T> list) {

   if (node == null) {

    return;
   }

   list.add(node.id);
   preOrderTraversal(node.left, list);
   preOrderTraversal(node.right, list);
  }

  /**
   * first visit left then current and then right node
   * Could be converted in non-recursive function using stack 
   * @param node
   * @param list
   */
  private void postOrderTraversal(BSTNode<T> node, LinkedList<T> list) {

   if (node == null) {

    return;
   }

   postOrderTraversal(node.left, list);
   postOrderTraversal(node.right, list);
   list.add(node.id);
  }

  /**
   * Level by level traversal using queue
   * 
   * @param node
   * @param list
   */
  private void breadthFirstTraveral(BSTNode<T> node, LinkedList<T> list) {

   LinkedList<BSTNode<T>> queue = new LinkedList<>();

   queue.offer(node);

   while (queue.size() != 0) {

    BSTNode<T> nodeToVisit = queue.poll();

    list.add(nodeToVisit.id);

    if (nodeToVisit.left != null)
     queue.offer(nodeToVisit.left);
    if (nodeToVisit.right != null)
     queue.offer(nodeToVisit.right);
   }

  }

 }

 /**
  * Binary tree model can used as BST also
  * 
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  private T id;

  private BSTNode<T> left;

  private BSTNode<T> right;

  public BSTNode(T id, BSTNode<T> left, BSTNode<T> right) {
   super();
   this.id = id;
   this.left = left;
   this.right = right;
  }

  @Override
  public String toString() {
   return "BSTNode [id=" + id + "]";
  }

 }

 @Test
 public void test() {

  // create empty BST
  BST<Integer> bst = new BST<>();

  // add nodes
  bst.add(4);

  bst.add(2);
  bst.add(5);

  bst.add(1);
  bst.add(3);

  bst.add(6);
  bst.add(7);

  // binary search tree in-order representation is 1,2,3,4,5,6,7 where
  // root is 4

  print(IteratorType.PRE_ORDER, bst.iterator(IteratorType.PRE_ORDER));

  print(IteratorType.IN_ORDER, bst.iterator(IteratorType.IN_ORDER));

  print(IteratorType.POST_ORDER, bst.iterator(IteratorType.POST_ORDER));

  print(IteratorType.BREATH_FIRST, bst.iterator(IteratorType.BREATH_FIRST));

 }

 private static void print(IteratorType type, Iterator<Integer> itr) {

  StringBuilder bld = new StringBuilder(type.name()).append(" ---> ");

  while (itr.hasNext()) {

   bld.append(itr.next()).append(" ,");
   
  }

  s_logger.info(bld.toString());

 }

}

Find maximum height or depth of binary tree. (Java Code)

Problem : Find the height of binary tree where tree might or might be complete .

Observations :

For complete BST

height = at most log2(total number of nodes)

or

h = long2(n)

So it is straight forward no traversal is needed , But if tree is not complete then we need to find height of all the leaves   and get maximum out of it .

We need to store only max value at any given time . Means we do not need caching of heights for each leaf..
We need to use depth first recursion as we need to calculate depth or height .

Algorithm Class : Recursion - back tracking


Java Code

package com.salpe.tree;

import java.util.logging.Logger;

import org.junit.Test;

/**
 * Find maximum height/depth of binary tree
 * Algorithm will be same for binary tree or binary search tree.
 */
public class BSTTest3 {

 // logger
 private static final Logger s_logger = Logger.getLogger(BSTTest2.class.getName());

 /**
  * Binary search tree pre-order list as 0,1,2,3,4,5,6
  */
 @Test
 public void test() {

  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);

  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);

  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);

  int maxHeight = bst.findMaxHeight();

  s_logger.info(Integer.toString(maxHeight));

 }

 /**
  * Binary Tree Node model
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  T data;
  BSTNode<T> left;
  BSTNode<T> right;

  BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {

   this.data = data;
   this.left = left;
   this.right = right;

  }

  @Override
  public String toString() {
   return "BSTNode [data=" + data + "]";
  }

 }

 /**
  * Binary Tree Representation
  *
  * @param <T>
  */
 static class BST<T extends Comparable<T>> {

  BSTNode<T> root;

  public BST(BSTNode<T> root) {
   this.root = root;
  }

  /**
   * @return max height or max depth of balanced or unbalanced binary
   *         tree.
   */
  public int findMaxHeight() {

   return depthFirstSearch0(root, 0);

  }

  /**
   * Need to traverse all tree because right/left most side might be max
   * length problem could be solved using dynamic programming also by
   * caching latest maximum height
   * 
   * @param node
   *            - root
   * @param currentHeight
   * @return maximum height of binary search tree.
   */
  public int depthFirstSearch0(BSTNode<T> node, int currentHeight) {

   if (node == null) {

    return currentHeight;
   }

   // increase height by 1 for increase in depth for recursion stack
   currentHeight++;

   // go left
   int leftMaxHeight = depthFirstSearch0(node.left, currentHeight);
   // then go right
   int rightMaxheight = depthFirstSearch0(node.right, currentHeight);

   // decrease height by 1 for decrease in depth for recursion stack
   currentHeight--;

   return Math.max(leftMaxHeight, rightMaxheight);

  }

 }

}

Find index of first one in series/array of zeros and ones where all zeros comes always before all ones. (Java Code )

Search/Find index of first one in series/array  of zeros and ones where all zeros comes always before all ones.

At least one is guaranteed in the series .
Length of array /series is not known .


Example :

Input :
01111111111111111111111111111..... length is not known
output : 1

Input :
00000000000000000000000011111111111.... length is not known
output :  25

Observations :

• Array is sorted .
• You can not use binary search as length is not known .
• Only option remains is sequential scan of zeros till first one is met .whose complexity will be O(n)
• There is zero before one which we are interested .
• Index of one is lowest which we are interested .

How to improve it ?

Lets say take random number or jump size as 10 .
Lets jump by 10 till you get first one . then always move to left with half of jum distance till you get 1 . Which ill be answer.

If we get  ArrayIndexOutOfBoundException then opt for sequential search .

Best  case solution could be  of complexity    (number of jumps  + log2( jump size))  ~ O(n) but better than previous O(n) .

Jump size could  optimized based on data if you have large number of zeros then take jump size large else something like 10 . This is data driven optimization .

This typical case of jump search for array or skip list  search .

There could be two flavors of problem say one with no length known other could be with known length is array .

Solution in java (length is not known )

package com.salpe.arrays;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 /**
  * Jump size is less than array size
  */
 @Test
 public void testSuccess1() {

  int[] arr = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 1 };

  int result1 = search(arr);

  Assert.assertEquals(8, result1);

 }

 /**
  * Jump size is equal to array size
  */
 @Test
 public void testSuccess2() {

  int[] arr = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };

  int result1 = search(arr);

  Assert.assertEquals(10, result1);

 }

 /**
  * Jump size is less than array size
  */
 @Test
 public void testSuccess3() {

  int[] arr = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };

  int result1 = search(arr);

  Assert.assertEquals(17, result1);

 }

 /**
  * Say length of array is not known Complexity is lon2(n)
  * 
  * @param arr
  * @return
  */
 public int search(int... arr) {

  // first decide possible segment
  // Jumping forth and back as per figure till we hit first one .

  // jump size depends on data , optimization is data dependent
  int jump = 10;

  int hi = 0;
  int lo = 0;
  int hiVal = -1;

  while (lo <= hi) {

   try {

    // jump forward
    hi = lo + jump;

    // test for out of index or NaN value
    hiVal  = arr[hi];

   } catch (ArrayIndexOutOfBoundsException arrayIndexOutOfBoundsException) {

    // jump half back
    jump = jump / 2;

    continue;

   }

   if (hiVal == 1) {
    break;
   }

   lo = hi;

  }

  // binary search between segment of possible size segment , segment/2 ,
  // segment/4 and so on
  return searchWithNoRecursion(arr, 1, lo, hi);
 }

 public int searchWithNoRecursion(int[] arr, int value, int lo, int hi) {

  while (lo <= hi) {

   int mid = (lo + hi) / 2;

   if (arr[mid] == value) {

    if (mid == 0) {

     return 0;

    }
    if (arr[mid - 1] == 0) {

     return mid;

    } else {

     hi = mid - 1;
    }

   } else {
    lo = mid + 1;

   }

  }

  // return is case no result found
  return -1;
 }

 public int searchWithRecursion(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   if (mid == 0) {

    return 0;

   }

   if (arr[mid - 1] == 0) {

    return mid;

   } else {

    return searchWithRecursion(arr, value, lo, mid - 1);

   }

  } else if (value < arr[mid]) {

   return searchWithRecursion(arr, value, lo, mid - 1);

  } else {

   return searchWithRecursion(arr, value, mid + 1, hi);
  }

 }

}

Solution in java (length is  known )

package com.salpe.arrays;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 @Test
 public void testSuccess1() {

  int[] arr = new int[] { 0, 0, 1, 1, 1 };

  int result1 = searchWithNoRecursion(arr, 1, 0, arr.length - 1);
  int result2 = searchWithRecursion(arr, 1, 0, arr.length - 1);

  Assert.assertEquals(2, result1);
  Assert.assertEquals(2, result2);

 }
 
 @Test
 public void testSuccess2() {

  int[] arr = new int[] { 0, 0, 0, 0, 1 };

  int result1 = searchWithNoRecursion(arr, 1, 0, arr.length - 1);
  int result2 = searchWithRecursion(arr, 1, 0, arr.length - 1);

  Assert.assertEquals(4, result1);
  Assert.assertEquals(4, result2);

 }
 
 @Test
 public void testSuccess3() {

  int[] arr = new int[] { 1, 1, 1, 1, 1 };

  int result1 = searchWithNoRecursion(arr, 1, 0, arr.length - 1);
  int result2 = searchWithRecursion(arr, 1, 0, arr.length - 1);

  Assert.assertEquals(0, result1);
  Assert.assertEquals(0, result2);

 }
 

 public int searchWithNoRecursion(int[] arr, int value, int lo, int hi) {

  while (lo <= hi) {

   int mid = (lo + hi) / 2;

   if (arr[mid] == value) {

    if (mid == 0) {

     return 0;

    }
    if (arr[mid - 1] == 0) {

     return mid;

    } else {

     hi = mid - 1;
    }

   } else {
    lo = mid + 1;

   }

  }

  // return is case no result found
  return -1;
 }

 public int searchWithRecursion(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   if (mid == 0) {

    return 0;

   }

   if (arr[mid - 1] == 0) {

    return mid;

   } else {

    return searchWithRecursion(arr, value, lo, mid - 1);

   }

  } else if (value < arr[mid]) {

   return searchWithRecursion(arr, value, lo, mid - 1);

  } else {

   return searchWithRecursion(arr, value, mid + 1, hi);
  }

 }

}

Find all paths with specified sum in binary tree. (Java code)

package com.salpe;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.logging.Logger;

import org.junit.Test;

public class BSTTest2 {

 private static final Logger s_logger = Logger.getLogger(BSTTest2.class.getName());

 /**
  * Binary tree pre-order list as 0,1,2,3,4,5,6
  */
 @Test
 public void test() {

  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);
  
  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);
  
  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);
  
  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);

  Collection<List<Integer>> result = bst.findAllPaths(12);

  for (List<Integer> list : result) {

   s_logger.info(list.toString());

  }

 }

 /**
  * Binary Tree Node model
  *
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  T data;
  BSTNode<T> left;
  BSTNode<T> right;

  BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {

   this.data = data;
   this.left = left;
   this.right = right;

  }

  @Override
  public String toString() {
   return "BSTNode [data=" + data + "]";
  }

 }

 /**
  * Binary Tree Representation
  *
  * @param <T>
  */
 static class BST<T extends Comparable<T>> {

  BSTNode<T> root;

  public BST(BSTNode<T> root) {
   this.root = root;
  }

  public Collection<List<T>> findAllPaths(int sum) {

   List<T> paths = new ArrayList<>();
   Collection<List<T>> result = new ArrayList<>();
   depthFirstSearch0(root, 0, sum, paths, result);
   return result;

  }

  public void depthFirstSearch0(BSTNode<T> node, int currentSum, int expectedSum, List<T> paths,
    Collection<List<T>> result) {

   if (node == null) {

    return;
   }

   paths.add(node.data);

   // check sum
   currentSum = currentSum + Integer.parseInt(node.data.toString());

   if (currentSum == expectedSum) {
    // add cloned list
    result.add(new ArrayList<>(paths));
   }
            // go left 
   depthFirstSearch0(node.left, currentSum, expectedSum, paths, result);
    // then go right
   depthFirstSearch0(node.right, currentSum, expectedSum, paths, result);

   // remove when going up in level
   paths.remove(paths.size() - 1);

  }

 }

}