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