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

Reverse Array Using Stack in Java

Stack can be used to reverse an array.

import java.util.Arrays;
import java.util.Stack;

public class ReverseArrayUsingStack {

 public static int[] reverse(int[] data) {

  Stack<Integer> stack = new Stack<Integer>();

  for (int i = 0; i < data.length; i++)
   stack.push(data[i]);

  for (int i = 0; i < data.length; i++)
   data[i] = stack.pop();

  return data;
 }

 public static void main(String[] args) {

  int[] a = { 41, 2, 151, 13, 43, 12 };

  System.out.println(Arrays.toString(a));

  System.out.println(Arrays.toString(reverse(a)));

 }
}

Initially push all the elements in the array onto the Stack. Stack is now full of items. Then pop all the elements from Stack back into original array.

In this solution, algorithm is not very efficient in terms of space because it uses an extra data structure to hold the items.

Computing Powers Recursively in Java

Recursion can be applied to raise a number x to an arbitrary non-negative integer n.

If the input integer is a large integer value then BigInteger can be used in Java.

Simple method to calculate the power of an integer can be implemented as follows :

public class ComputingPowers {

 public static int power(int number, int exp)
 {
  if( exp == 0 )
   return 1;
  else
   return number*power(number, exp-1);
 }
 
 public static void main(String[] args) {
  
  System.out.println(power(2,6));
 }
 
}

This is one of the recursive solutions to calculate the power of an integer in Java.

There is a better algorithm which employs squaring technique. Advantage of using squaring technique is that it has got a better performance in terms of both time and space when compared to above implementation.

Squaring technique results in:

Time Complexity = O(logN)
Space Complexity = O(logN)

Reference :  http://www.amazon.com/Data-Structures-Algorithms-Java-Edition-ebook/dp/B00JDRQF8C

Binary Recursive Sum of Integer Array in Java

Binary recursion is one of the common methods where inside the current method two recursive method calls are being made to itself recursively.

Sum of all the elements of an integer array can be achieved by using binary recursion.

Binary recursion can be applied to sum elements of an array as follows :

Sum the elements in the first half recursively and sum the elements in the second half recursively. Then add this two sums to find the total sum.

Space complexity = O(logN)
Time complexity = O(N)

public class BinaryRecursiveSumOfArray {

    public static int binaryRecursiveSum( int[] data, int low, int high )
    {  
       if( low>high )
         return 0;
       else if( low == high )
         return data[low];
       else
       {
         int mid = (low+high)/2;
         return binaryRecursiveSum(data, low, mid)+binaryRecursiveSum(data, mid+1, high);
       }
    } 
 
    public static void main(String[] args) {
 
        int[] data =  {1,2,3,4,5,6,7,8};
  
        int result = binaryRecursiveSum(data, 0, data.length-1);
  
        System.out.println(result);  
    }
 
}

For an 8 element array following recursion trace is obtained.

Reference :  http://www.amazon.com/Data-Structures-Algorithms-Java-Edition-ebook/dp/B00JDRQF8C

Reverse Integer Array Recursively in Java

Recursion can be used to reverse an integer array without allocating a new array.

This method is more space efficient than the solution which creates a new array to hold the reversed one.

By starting from the specific start index to end index inclusively, following method enables to reverse items at specific array index recursively.

public class ReverseArray {

 public static void reverseArray( int[] data, int low, int high )
 {
  if( low<high )
  {
   int temp = data[low];
   data[low] = data[high];
   data[high] = temp;
   reverseArray(data, low+1, high-1);   
  }  
 }
 
 public static void main(String[] args) {
  
  int[] arr = {4,3,6,2,7,8,9,5};
  
  for (int i = 0; i < arr.length; i++) {
   
   System.out.print(arr[i]+" ");   
  }
  
  System.out.println();
  
  reverseArray(arr, 1, 3);
  
  for (int i = 0; i < arr.length; i++) {
   
   System.out.print(arr[i]+" ");   
  }  
  
 }
}

Sample input and output arrays can be used :

Reference :  http://www.amazon.com/Data-Structures-Algorithms-Java-Edition-ebook/dp/B00JDRQF8C

Recursive Sum of the First n Elements of an Array in Java

We assume that input is a non-zero length integer array.

Base case (Termination condition) : if n == 0 then return 0

General case : return the sum of the first n-1 integers in the array plus the value at the specified index in the array

For the input array {1, 3, 5, 4, 7} find the sum of the first 4 items in the array recursively.

Result is the sum of the items =  1+3+5+4=13

public class SumOfNIntegers {

 
 public static int recursiveArraySum(int[] data, int n)
 {
  if( n==0 )
   return 0;
  else
   return recursiveArraySum(data, n-1) + data[n-1];
 }
 
 public static void main(String[] args) {
  
  int[] inputArray = {1, 3, 5, 4, 7};
  
  int result = recursiveArraySum(inputArray, 3);
  
  System.out.println(result);
  
  result = recursiveArraySum(inputArray, 4);
  
  System.out.println(result);
  
 } 
}

recursiveArraySum method takes input array and the number of items to sum from the beginning of the array.

Console output is :

9

13


Diagram for the recursive method calls :

Reference :  http://www.amazon.com/Data-Structures-Algorithms-Java-Edition-ebook/dp/B00JDRQF8C