Static Generic Recursive Binary Search Algorithm In Java

Binary Search algorithm can be implemented recursively in a generic way in Java.

Generic recursive binary search method accepts input parameters as any item that implements Comparable interface.

Static binary search method was tested with Integer, Double and String type of parameters where each of them individually implements Comparable interface.

package basics;

import java.util.Arrays;

public class GenericRecursiveBinarySearch {

  public static <T extends Comparable<T>> int index( T[] items, T item )
  {
      return index( items, item, 0, items.length-1 );
  }
  
  public static <T extends Comparable<T>> int index( T[] items, T key, int low, int high )
  {
      if ( key == null )
          return -1;
   
      if( low > high  )
          return -1;
    
      int mid = low+(high-low)/2;
    
      if( key.compareTo( items[mid] ) > 0 )
          return index(items, key, mid+1, high);
      else if( key.compareTo( items[mid] ) < 0 )
          return index( items, key, low, mid-1 );
      else
          return mid;
  }  

  public static void main(String[] args) {

      Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

      Arrays.sort(items);
      System.out.print("Sorted Integer Array = ");
      for (Integer item : items) {
           System.out.print(item+" ");
      }
  
      int foundIndex = index(items, Integer.valueOf(22));
      System.out.println("\nInteger Array Contains item 22 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(11));
      System.out.println("Integer Array Contains item 11 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(67));
      System.out.println("Integer Array Contains item 67 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(10));
      System.out.println("Integer Array Contains item 10 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(101));
      System.out.println("Integer Array Contains item 101 at index = " + foundIndex);

      foundIndex = index(items, null);
      System.out.println("Integer Array Contains item null at index = " + foundIndex);

      String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
      Arrays.sort(strItems);

      System.out.print("\nSorted String Array = ");
      for (String item : strItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(strItems, "alk");
      System.out.println("\nString Array Contains item alk at index = " + foundIndex);

      foundIndex = index(strItems, "nhy");
      System.out.println("String Array Contains item nhy at index = " + foundIndex);

      foundIndex = index(strItems, "zyt");
      System.out.println("String Array Contains item zyt at index = " + foundIndex);

      foundIndex = index(strItems, "zyts");
      System.out.println("String Array Contains item zyts at index = " + foundIndex);

      foundIndex = index(strItems, "null");
      System.out.println("String Array Contains item null at index = " + foundIndex);

      Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
      Arrays.sort(dItems);

      System.out.print("\nSorted Double Array = ");
      for (Double item : dItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(dItems, 13.3);
      System.out.println("\nDouble Array Contains item 13.3 at index = " + foundIndex);

      foundIndex = index(dItems, 14.3);
      System.out.println("Double Array Contains item 14.3 at index = " + foundIndex);

      foundIndex = index(dItems, 23.0);
      System.out.println("Double Array Contains item 23.0 at index = " + foundIndex);

 }
}

Binary search works for sorted arrays so before calling binary search on arrays call Arrays.sort to sort array items.

Create a GenericRecursiveBinarySearch.java file in your workspace.

When the main method inside the GenericRecursiveBinarySearch class executed it is going to print :

Sorted Integer Array = 10 11 22 32 55 56 66 67 89 95
Integer Array Contains item 22 at index = 2
Integer Array Contains item 11 at index = 1
Integer Array Contains item 67 at index = 7
Integer Array Contains item 10 at index = 0
Integer Array Contains item 101 at index = -1
Integer Array Contains item null at index = -1

Sorted String Array = abc adk alk fre nhy zyt
String Array Contains item alk at index = 2
String Array Contains item nhy at index = 4
String Array Contains item zyt at index = 5
String Array Contains item zyts at index = -1
String Array Contains item null at index = -1

Sorted Double Array = 6.0 9.6 11.3 13.3 23.2 45.7
Double Array Contains item 13.3 at index = 3
Double Array Contains item 14.3 at index = -1
Double Array Contains item 23.0 at index = -1

Static Generic Iterative Binary Search Algorithm In Java

In order take advantage of Generics in Java, binary search method can be implemented generically.

Binary search works for sorted Arrays so Arrays.sort method is used before using binarySearch method.

Any type that implements Comparable interface is accepted by the generic iterative search method.

Built-in String, Integer and Double classes in Java implement Comparable interface so search method accepts these parameters.

package basics;

import java.util.Arrays;

public class GenericIterativeBinarySearch {

 public static <T extends Comparable<T>> boolean search( T[] items, T item ) {

  if (item == null) {
   return false;
  }

  int low = 0;
  int high = items.length - 1;

  while (low <= high) {

   int ix = low + (high - low) / 2;

   if (item.compareTo(items[ix]) < 0) {
    high = ix - 1;
   } else if (item.compareTo(items[ix]) > 0) {
    low = ix + 1;
   } else {
    return true;
   }
  }

  return false;
 }


 public static void main(String[] args) {

  Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

  Arrays.sort(items);

  boolean found = search(items, Integer.valueOf(22) );
  System.out.println("Integer Array Contains item 22 = "+found);

  found = search(items, Integer.valueOf(11) );
  System.out.println("Integer Array Contains item 11 = "+found);

  found = search(items, Integer.valueOf(67) );
  System.out.println("Integer Array Contains item 67 = "+found);

  found = search(items, Integer.valueOf(10) );
  System.out.println("Integer Array Contains item 10 = "+found);

  found = search(items, Integer.valueOf(101) );
  System.out.println("Integer Array Contains item 101 = "+found);  
  
  found = search(items, null );
  System.out.println("Integer Array Contains item null = "+found); 
  
  String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
  Arrays.sort(strItems);
  
  found = search( strItems, "alk" );
  System.out.println("String Array Contains item alk = "+found);
  
  found = search( strItems, "nhy" );
  System.out.println("String Array Contains item nhy = "+found);
  
  found = search( strItems, "zyt" );
  System.out.println("String Array Contains item zyt = "+found);
  
  found = search( strItems, "zyts" );
  System.out.println("String Array Contains item zyts = "+found);
  
  found = search( strItems, "null" );
  System.out.println("String Array Contains item null = "+found);
  
  Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
  Arrays.sort(dItems);
  
  found = search( dItems, 13.3 );
  System.out.println("Double Array Contains item 13.3 = "+found);
  
  found = search( dItems, 14.3 );
  System.out.println("Double Array Contains item 14.3 = "+found);
  
  found = search( dItems, 23.0 );
  System.out.println("Double Array Contains item 23.0 = "+found);  
  
 }
}

Create a GenericIterativeBinarySearch.java file in your workspace.

When the main method inside the GenericIterativeBinarySearch class executed it is going to print :

Integer Array Contains item 22 = true
Integer Array Contains item 11 = true
Integer Array Contains item 67 = true
Integer Array Contains item 10 = true
Integer Array Contains item 101 = false
Integer Array Contains item null = false
String Array Contains item alk = true
String Array Contains item nhy = true
String Array Contains item zyt = true
String Array Contains item zyts = false
String Array Contains item null = false
Double Array Contains item 13.3 = true
Double Array Contains item 14.3 = false
Double Array Contains item 23.0 = false

Generic Method to Print Array Elements in Java

Generics in Java enable programmers to provide compile-time type-safety.

There are some main benefits of using generics in Java such as :

1-) Strong type-checking
2-) Elimination of casts
3-) Provide a way to develop generic algorithms

Methods can also be designed in a generic fashion in Java, too. Following generic method prints all the elements of an array one-by-one in a for-loop for both wrapper types and custom defined types.

package basics;

public class GenericPrint {

 static class Employee
 {
  String name;
  Employee(String pName)
  {
   name = pName;
  }
  
  public String toString() {
   return "[Employee Name = "+name+" ]";
  }
 }
 
 // Generic method
 public static <T> void print( T[] inParam )
 {
  for( T t: inParam )
  {
   System.out.printf("%s ", t);
  }
 }
 
 
 public static void main(String[] args) {
  
  String[] strArr = {"D1","D2","D3","D4"};  
  print(strArr);
  
  Integer[] intArr = { 1,2,3 };
  System.out.println();
  print(intArr);
  
  Double[] dArr = { 5.5, 6.6, 7.7 };
  System.out.println();
  print(dArr);
    
  Employee e1 = new Employee("Emply1");
  Employee e2 = new Employee("Emply2");
  Employee e3 = new Employee("Emply3");
  
  Employee[] empArr = { e1, e2, e3 };
  
  System.out.println();
  print(empArr);  
 } 
}

Create a GenericPrint.java file in your workspace.

When the main method inside the GenericPrint class executed it is going to print :

D1 D2 D3 D4
1 2 3
5.5 6.6 7.7
[Employee Name = Emply1 ] [Employee Name = Emply2 ] [Employee Name = Emply3 ]

Generic NonRecursive BottomUp Merge Sort in Java

MergeSort can also be implemented with a non-recursive bottom-up approach.

Non-recursive bottom-up merge-sort runs in O(nlogn) time as recursive version does.

It is considered a bit faster than recursive merge-sort in practice because it does not make recursive-calls.

There is a detailed description about this implementation at here.

package interviewquestions;

import java.util.Comparator;

public class MergeSortRoutine {

 public static <K> void merge(K[] in, K[] out, Comparator<K> comp, int start, int inc) {

  int end1 = Math.min(start + inc, in.length);
  int end2 = Math.min(start + 2 * inc, in.length);
  int x = start;
  int y = start + inc;
  int z = start;
  
  while (x < end1 && y < end2)
   if (comp.compare(in[x], in[y]) < 0)
    out[z++] = in[x++];
   else
    out[z++] = in[y++];
  
  if (x < end1)
   System.arraycopy(in, x, out, z, end1 - x);
  else if (y < end2)
   System.arraycopy(in, y, out, z, end2 - y);
 }

 public static <K> void mergeSortBottomUp(K[] orig, Comparator<K> comp) {
  
  int n = orig.length;
  K[] src = orig;
  K[] dest = (K[]) new Object[n];
  K[] temp;
  for (int i = 1; i < n; i *= 2) { 
   
   for (int j = 0; j < n; j += 2 * i)
    merge(src, dest, comp, j, i);
   
   temp = src;
   src = dest;
   dest = temp;
  }
  if (orig != src)
   System.arraycopy(src, 0, orig, 0, n);
 }

 private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
  public int compare(T a, T b) {
   return a.compareTo(b);
  }
 }

 public static void main(String[] args) {

  Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };

  System.out.println("Before sorting integer array with generic mergesort ");
  for (int i = 0; i < inputArr.length; i++) {
   System.out.print(inputArr[i] + " ");
  }

  mergeSortBottomUp(inputArr, new IntComparator<Integer>());

  System.out.println("\nAfter sorting integer array with generic mergesort ");
  for (int i = 0; i < inputArr.length; i++) {
   System.out.print(inputArr[i] + " ");
  }

  String[] values = { "asd", "basd", "cwe", "awe", "vasd" };

  System.out.println("\n\nBefore sorting String array with generic mergesort ");
  for (int i = 0; i < values.length; i++) {
   System.out.print(values[i] + " ");
  }

  mergeSortBottomUp(values, new IntComparator<String>());

  System.out.println("\nAfter sorting String array with generic mergesort ");
  for (int i = 0; i < values.length; i++) {
   System.out.print(values[i] + " ");
  }
  
 }
}

Above Non-recursive bottom-up Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSortBottomUp method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd

Generic Recursive Merge Sort in Java

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. 

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Merge sort animation. The sorted elements are represented by dots.

package interviewquestions;

import java.util.Arrays;
import java.util.Comparator;

public class MergeSortRoutine {

   public static <K> void merge(K[] S1, K[] S2, K[] S, Comparator<K> comp) {

     int i = 0, j = 0;
     while (i + j < S.length) {
         if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0))
            S[i + j] = S1[i++]; 
         else
            S[i + j] = S2[j++]; 
     }

   }

   public static <K> void mergeSort(K[] S, Comparator<K> comp) {

     int n = S.length;
     if (n < 2)
        return; 

     int mid = n / 2;
     K[] S1 = Arrays.copyOfRange(S, 0, mid); 
     K[] S2 = Arrays.copyOfRange(S, mid, n);

     mergeSort(S1, comp); 
     mergeSort(S2, comp);

     merge(S1, S2, S, comp);
   }

   private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
     public int compare(T a, T b) {
      return a.compareTo(b);
     } 
   }

   public static void main(String[] args) {

     Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };  
  
     System.out.println("Before sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
    
     mergeSort( inputArr, new IntComparator<Integer>() );
  
     System.out.println("\nAfter sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
  
     String[] values = { "asd","basd","cwe", "awe", "vasd" };
  
     System.out.println("\n\nBefore sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
  
     mergeSort(values, new IntComparator<String>());
  
     System.out.println("\nAfter sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
   }
}

Above Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSort method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd

Generic Recursive Find Depth of Binary Tree in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Depth of a binary tree is defined as the maximum length of all paths.

If a binary tree has only one node, its depth is 1. Following sample binary tree can be used as a test input.

There is a detailed and helpful description also at this link. 

package interviewquestions;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public int depth() {
       return depth(root);
   }

   private int depth(Node<T> pNode) {
  
     if (pNode == null)
         return 0;

     int left = depth(pNode.getLeftChild());
     int right = depth(pNode.getRightChild());
       
     int result = (left>right) ? (left+1) : (right+1);
     return result;
   }
  
}

public class BinaryTreeOperations {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    System.out.println("Depth of Binary Tree = "+binaryTree.depth()); 
 }

}

Create a BinaryTreeOperations.java file in your workspace.

When the main method inside the BinaryTreeOperations class executed it is going to print :

Depth of Binary Tree = 3

Generic Iterative Depth-First Binary Tree Traversal with Stack in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root(selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS requires the use of a data structure called Stack, which is a Last In First Out (LIFO) structure.

                                       Depth-First Traversal Sequence: 1 - 2 - 4 - 5 - 3 - 6

package interviewquestions;

import java.util.Stack;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void depthFirst()
   {
     depthFirst( root );   
   }
 
   private void depthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Stack<Node<T>> stack = new Stack<Node<T>>();
     stack.add(pNode);

     while (!stack.isEmpty()) {
         Node<T> node = stack.pop();

         if (node.getRightChild() != null)
             stack.add(node.getRightChild());
         if (node.getLeftChild() != null)
             stack.add(node.getLeftChild());
         System.out.print(node.getData());
     }

   }
  
}

public class DepthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.depthFirst();  
 }

}

Create a DepthFirstTraversal.java file in your workspace.

When the main method inside the DepthFirstTraversal class executed it is going to print :

1
2
4
5
3
6

Generic Iterative Breadth-First Binary Tree Traversal with Queue in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors. 

Breadth-first traversal is also known as level-order traversal. BFS requires the use of a data structure called Queue, which is a First In First Out (FIFO) structure.

                                         Breadth-First Traversal Sequence: 1 - 2 - 3 - 4 - 5 - 6

package interviewquestions;

import java.util.LinkedList;
import java.util.Queue;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void breadthFirst()
   {
     breadthFirst( root );   
   }
 
   private void breadthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Queue<Node<T>> queue = new LinkedList<Node<T>>();
     queue.add((Node<T>) pNode);
  
     while (!queue.isEmpty()) {
          Node<T> node = (Node<T>) queue.remove();
          System.out.print(" " + node.getData());
   
          if (node.getLeftChild()!= null)
              queue.add(node.getLeftChild());
          if ( node.getRightChild() != null)
              queue.add(node.getRightChild());
     }      

   }
  
}

public class BreadthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.breadthFirst();  
 }

}

Create a BreadthFirstTraversal.java file in your workspace.

When the main method inside the BreadthFirstTraversal class executed it is going to print :

1
2
3
4
5
6

Generic Recursive Inorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Inorder traversal allows all the nodes of the binary tree to be visited by applying a recursive algorithm.

This can be summed up as

1. Traverse left subtree
2. Visit root node (output this)
3. Traverse right subtree

Recursive inorder binary tree traversal algorithm can use a generic node class.

                                                 Inorder Traversal Sequence: 4 - 2 - 5 - 1 - 3 - 6

package interviewquestions;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void inOrder()
   {
     inOrder( root );   
   }
 
   private void inOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     inOrder( pNode.getLeftChild() );
     System.out.println( pNode.getData() );
     inOrder( pNode.getRightChild() );       

   }
  
}

public class InOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.inOrder();  
 }

}

Create a InOrderTraversal.java file in your workspace.

When the main method inside the InOrderTraversal class executed it is going to print :

4
2
5
1
3
6

Generic Recursive Postorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Postorder traversal allows all the nodes of the binary tree to be visited by applying a recursive algorithm.

This can be summed up as

1. Traverse left subtree
2. Traverse right subtree
3. Visit root node (output this)

Recursive postorder binary tree traversal algorithm can use a generic node class.

Postorder Traversal Sequence: 4 - 5 - 2 - 6 - 3 - 1

package interviewquestions;


class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void postOrder()
   {
     postOrder( root );   
   }
 
   private void postOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     postOrder( pNode.getLeftChild() );
     postOrder( pNode.getRightChild() );

     System.out.println( pNode.getData() );  

   }
  
}

public class PostOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.postOrder();  
 }

}

Create a PostOrderTraversal.java file in your workspace.

When the main method inside the PostOrderTraversal class executed it is going to print :

4
5
2
6
3
1

Generic Recursive Preorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Preorder traversal allows all the nodes of the binary tree to be visited by starting from the root node.

Recursive preorder binary tree traversal algorithm can use a generic node class.

                                                         Preorder Traversal Sequence: 1 - 2 - 4 - 5 - 3 - 6

package interviewquestions;


class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }
}

class BinaryTree<T>
{

   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void preOrder()
   {
     preOrder( root );   
   }
 
   private void preOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   
     System.out.println( pNode.getData() );  
  
     preOrder( pNode.getLeftChild() );
     preOrder( pNode.getRightChild() );
   }
  
}

public class PreOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.preOrder();  
 }

}

Create a PreOrderTraversal.java file in your workspace.

When the main method inside the PreOrderTraversal class executed it is going to print :

1
2
4
5
3
6