trjhtr

I'm trying to find the complexity of this code and some suggestions for improving the code quality. and handling the code gracefully, esp in the areas of exception handling, checking edge cases, presentation, etc.

// Node Class

class Node 
 int id;
 Node left;
 Node right;
 Node(int id) 
 this.id = id;
 left = null;
 right = null;
 

// ArrayIntoBinaryTree Class

import java.util.Scanner;
public class ArrayIntoBinaryTree 

 /*
 Algorithm:
 1. Insert into the tree the middle element of the array.
 2. Insert (into the left subtree) the left subarray elements
 3. Insert (into the right subtree) the right subarray elements
 4. Recurse
 */

 ArrayIntoBinaryTree arrayIntoBinaryTree = new ArrayIntoBinaryTree();

 public static void main(String args) 
 int arr = initializeArray();
 if (arr == null) 
 throw new NullPointerException("Input array is empty");
 
 Node node = addToTree(arr, 0, arr.length);
 

 // find Subarray - Use Recursion. 
 static Node addToTree(int arr, int first, int last) 
 // Exit condition
 if(first<last) 
 return null;
 
 int midElement = arr[(first+last)/2];
 Node newNode = new Node(arr[midElement]);
 newNode.left = addToTree(arr, first, midElement-1);
 newNode.right = addToTree(arr, midElement+1, last);
 return newNode;
 

 static int initializeArray() 
 Scanner sc = new Scanner(System.in);
 System.out.println("Enter the size of array: ");
 int size = sc.nextInt();

 if (size < 1) 
 return null;
 

 System.out.println("Now enter " + size + " number of elements.");
 int arr = new int[size];
 for(int i=0; i<size; i++) 
 arr[i] = sc.nextInt();
 
 return arr;
 

Bug 1

if(first<last) 
 return null;

This is wrong. It will return a null for the very root of the tree. Change to

if (last - first < 1) 
 return null;

Bug 2

int midElement = arr[(first+last)/2];
Node newNode = new Node(arr[midElement]);
newNode.left = addToTree(arr, first, midElement-1);
newNode.right = addToTree(arr, midElement+1, last);

This is wrong too. You should have instead:

int middleIndex = (first + last) / 2;
Node newNode = new Node(arr[middleIndex]);
newNode.left = addToTree(arr, first, middleIndex);
newNode.right = addToTree(arr, middleIndex + 1, last);

Advice 1

if(first<last) 
 ...

According to Java coding conventions, you must have a single space after if and before an opening (. Also, each binary operator must have a single space before and after it. Putting things together, you must write

if (first < last) 
 ...

Advice 2

I suggest you move the tree node to its own file and declare it non-public. Also, I suggest you roll a public tree type that can validate that data is traversed in-order in the same order as the elements in the input array.

Alternative implementation

IntBinaryTreeNode.java

final class IntBinaryTreeNode 

 private int datum;
 private IntBinaryTreeNode leftChild;
 private IntBinaryTreeNode rightChild;

 IntBinaryTreeNode(int datum) 
 this.datum = datum;
 

 int getDatum() 
 return datum;
 

 IntBinaryTreeNode getLeftChild() 
 return leftChild;
 

 IntBinaryTreeNode getRightChild() 
 return rightChild;
 

 void setLeftChild(IntBinaryTreeNode leftChild) 
 this.leftChild = leftChild;
 

 void setRightChild(IntBinaryTreeNode rightChild) 
 this.rightChild = rightChild;
 

IntBinaryTree.java

import java.util.function.Consumer;

/**
 * Implements a simple binary tree in which each node contains an integer. This
 * implementation does not enforce any order so it is not a binary search tree.
 */
public class IntBinaryTree 

 private final IntBinaryTreeNode root;

 IntBinaryTree(IntBinaryTreeNode root) 
 this.root = root;
 

 public void inOrderTraversal(Consumer<Integer> consumer) 
 inOrderTraversal(root, consumer);
 

 private void inOrderTraversal(IntBinaryTreeNode node, 
 Consumer<Integer> consumer) 
 if (node == null) 
 return;
 

 inOrderTraversal(node.getLeftChild(), consumer);
 consumer.accept(node.getDatum());
 inOrderTraversal(node.getRightChild(), consumer);
 

IntArrayToBinaryTreeConverter.java

 public final class IntArrayToBinaryConverter 

 public IntBinaryTree convert(int array) 
 IntBinaryTreeNode root = convert(array, 0, array.length);
 return new IntBinaryTree(root);
 

 /**
 * Converts a range @code array[fromIndex], ..., array[toIndex - 1] into
 * a binary search tree.
 * 
 * @param array the array of integers to convert into nodes.
 * @param fromIndex the starting, inclusive index of the range to convert.
 * @param toIndex the ending, exclusive index of the range to convert.
 * @return 
 */
 private IntBinaryTreeNode convert(int array,
 int fromIndex, 
 int toIndex) 
 int rangeLength = toIndex - fromIndex;

 if (rangeLength < 1) 
 return null;
 

 int middleIndex = fromIndex + ((toIndex - fromIndex) >>> 1);
 IntBinaryTreeNode node = 
 new IntBinaryTreeNode(array[middleIndex]);
 node.setLeftChild(convert(array, fromIndex, middleIndex));
 node.setRightChild(convert(array, middleIndex + 1, toIndex));
 return node;
 

Main.java

import java.util.Scanner;

public class Main 

 public static void main(String args) 
 Scanner scanner = new Scanner(System.in);
 System.out.print("Enter the array length: ");
 int arrayLength = scanner.nextInt();
 System.out.print("Enter all the array components: ");
 int array = new int[arrayLength];

 for (int i = 0; i < arrayLength; ++i) 
 array[i] = scanner.nextInt();
 

 IntBinaryTree tree = 
 new IntArrayToBinaryConverter().convert(array);

 tree.inOrderTraversal(System.out::println);