Reconstruct a binary tree given its Inorder and Preorder traversals in Java

This is one of the interesting problems that I encountered recently. Given two sequences one being an in-order traversed sequence and other being a pre-ordered traversed sequence, a binary tree has to be reconstructed out of it.

This is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.

Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.

Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I

I tweaked a bit from this source for UI.

package dsa.btree;

import javax.swing.JFrame;

public class PreOrderInOrderReconstructor {
 public static void main(String[] args) {
  PreOrderInOrderReconstructor pir = new PreOrderInOrderReconstructor();
  String[] preOrderSequence = { "A", "B", "D", "E", "C", "F", "G", "H", "I" };
  String[] inOrderSequence = { "D", "B", "E", "A", "F", "C", "H", "G", "I" };
  Node root = pir.reConstruct(preOrderSequence, 0,
    preOrderSequence.length - 1, inOrderSequence, 0,
    inOrderSequence.length - 1);
  JFrame f = new JFrame("BinaryTree");
  f.getContentPane().add(new BinaryTreeView(root));
  f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  f.setBounds(50, 50, 400, 400);
  f.setVisible(true);
 }

 private Node reConstruct(String[] preOrderSequence, int pMin, int pMax,
   String[] inOrderSequence, int iMin, int iMax) {
  if ((pMax - pMin) < 0) {
   return null;
  }
  if ((pMax - pMin) == 0) {
   return new Node(preOrderSequence[pMin]);
  }
  Node n = new Node(preOrderSequence[pMin]);
  int inorderPos = findInOrderPos(inOrderSequence,
    preOrderSequence[pMin], iMin, iMax);
  int leftBias = inorderPos - iMin;
  n.addLeft(reConstruct(preOrderSequence, pMin + 1, pMin + leftBias,
    inOrderSequence, iMin, iMin + leftBias - 1));
  n.addRight(reConstruct(preOrderSequence, pMin + leftBias + 1, pMax,
    inOrderSequence, iMin + leftBias + 1, iMax));
  return n;
 }

 private int findInOrderPos(String[] inOrderSequence, String string,
   int minIndex, int maxIndex) {
  for (int i = minIndex; i < maxIndex; i++) {
   if (inOrderSequence[i].equals(string)) {
    return i;
   }
  }
  return -1;
 }
}

The Node structure

package dsa.btree;

/**
 * A class representing one node of the tree.
 */
public class Node {
 private String content = null;
 private Node left = null;
 private Node right = null;
 
 public Node(String c) {
  this.content = c;
 }
 
 public String getContent() { return content; }
 
 public Node getLeft() { return left; }
 
 public Node setLeft(String content) {
  left = new Node(content);
  return left;
 }
 
 public Node getRight() { return right; }
 
 public void addRight(Node reConstruct) {
  this.right = reConstruct;
 }

 public void addLeft(Node reConstruct) {
  this.left = reConstruct;
 }
}

The code for UI

package dsa.btree;

import java.awt.Dimension;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.util.HashMap;
import javax.swing.JPanel;

public class BinaryTreeView extends JPanel {
 
 private static final long serialVersionUID = 1L;
 private Node root = null;
 private HashMap<Node, Rectangle> nodeLocations = null;
 private HashMap<Node, Dimension> subtreeSizes = null;
 private boolean dirty = true;
 private int parent2child = 20, child2child = 30;
 
 private Dimension empty = new Dimension(0, 0);
 private FontMetrics fm = null;
 
 public BinaryTreeView(Node root) {
  this.root = root;
  nodeLocations = new HashMap<Node, Rectangle>();
  subtreeSizes = new HashMap<Node, Dimension>();
 }
 
 private void calculateLocations() {
  nodeLocations.clear();
  subtreeSizes.clear();
  if (root != null) {
   calculateSubtreeSize(root);
   calculateLocation(root, Integer.MAX_VALUE, Integer.MAX_VALUE, 0);
  }
 }
 
 private Dimension calculateSubtreeSize(Node n) {
  if (n == null) return new Dimension(0, 0);
  Dimension ld = calculateSubtreeSize(n.getLeft());
  Dimension rd = calculateSubtreeSize(n.getRight());
  int h = fm.getHeight() + parent2child + Math.max(ld.height, rd.height);
  int w = ld.width + child2child + rd.width;
  Dimension d = new Dimension(w, h);
  subtreeSizes.put(n, d);
  return d;
 }
 
 private void calculateLocation(Node n, int left, int right, int top) {
  if (n == null) return;
  Dimension ld = (Dimension) subtreeSizes.get(n.getLeft());
  if (ld == null) ld = empty;
  Dimension rd = (Dimension) subtreeSizes.get(n.getRight());
  if (rd == null) rd = empty;
  int center = 0;
  if (right != Integer.MAX_VALUE)
   center = right - rd.width - child2child/2;
  else if (left != Integer.MAX_VALUE)
   center = left + ld.width + child2child/2;
  int width = fm.stringWidth(n.getContent().toString());
  Rectangle r = new Rectangle(center - width/2 - 3, top, width + 6, fm.getHeight());
  nodeLocations.put(n, r);
  calculateLocation(n.getLeft(), Integer.MAX_VALUE, center - child2child/2, top + fm.getHeight() + parent2child);
  calculateLocation(n.getRight(), center + child2child/2, Integer.MAX_VALUE, top + fm.getHeight() + parent2child);
 }
 
 private void drawTree(Graphics2D g, Node n, int px, int py, int yoffs) {
  if (n == null) return;
  Rectangle r = (Rectangle) nodeLocations.get(n);
  g.draw(r);
  g.drawString(n.getContent().toString(), r.x + 3, r.y + yoffs);
  if (px != Integer.MAX_VALUE)
   g.drawLine(px, py, r.x + r.width/2, r.y);
  drawTree(g, n.getLeft(), r.x + r.width/2, r.y + r.height, yoffs);
  drawTree(g, n.getRight(), r.x + r.width/2, r.y + r.height, yoffs);
 }
 
 public void paint(Graphics g) {
  super.paint(g);
  fm = g.getFontMetrics();
  if (dirty) {
   calculateLocations();
   dirty = false;
  }
  Graphics2D g2d = (Graphics2D) g;
  g2d.translate(getWidth() / 2, parent2child);
  drawTree(g2d, root, Integer.MAX_VALUE, Integer.MAX_VALUE, fm.getLeading() + fm.getAscent());
  fm = null;
 }
 
}

Hope you learnt something today along with me.

Cheers!
Braga

Given a sorted array, find k in least possible time in Java

Given a sorted array and a value k, write a program to find whether that number is present in that array or not.

The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.

This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.

package dsa.arrays;

public class SortedFindK {
 
 public static void main(String[] args) {
  SortedFindK ssfm = new SortedFindK();
  ssfm.findKOfArray(null, 7);
  ssfm.findKOfArray(new int[]{1,4,6,7,45,78,88}, 45);
  ssfm.findKOfArray(new int[]{1,2,3,4,5,6,8,9,14}, 99);
  ssfm.findKOfArray(new int[]{-1,0,1,2,3,4,5}, 2);
  ssfm.findKOfArray(new int[]{1,2,3,4,5}, 5);
  ssfm.findKOfArray(new int[]{}, 3);
  ssfm.findKOfArray(new int[]{1}, 9);
 }
  
 public void findKOfArray(int[] csArray, int k){
  if(csArray == null || csArray.length == 0) { 
   System.out.print("\nHave some dignity. Send a valid array with at least 1 element");
   return;
  }
  int length = csArray.length;
  System.out.print("\n"+findKRecursively(csArray, 0 , length-1, k));
 }
 
 public boolean findKRecursively (int[] arr, int start, int end, int k){
  if(arr[start]==k || arr[end]==k){
   return true;
  }
  if(k > arr[start] && k < arr[end]){
   if(k <= arr[end/2]){
    return findKRecursively(arr, start, end/2, k);
   }else{
    return findKRecursively(arr, end/2 + 1, end, k);
   }
  }else{
   return false;
  }
 }
 
}
/*
Have some dignity. Send a valid array with at least 1 element
true
false
true
true
Have some dignity. Send a valid array with at least 1 element
false
*/

Leave some comments if you have anything to say.

Cheers!
Braga

Find middle element in a circularly sorted array

Given a circularly sorted array, find its middle element in best possible time.

A circularly sorted array is an array that is obtained by shifting an array k times. For example, the following is a circularly sorted array,

[5, 6, 7, 8, 9, 1, 2, 3, 4]

If you sort this array and find the middle element it will be 5. But then, sorting is a painful operation which will take O(nlogn) timing. So it is out of the equation right away. If you closely observe this problem, it is enough to find the shifting index, the place where the sorting varies. For example, the shifting index in the above example is 5.  Once that is found, then it is a matter of applying the bias over the length.

This program can be attacked in a recursive manner. Take the first and last elements in the array and compare them. If they are sorted, then the last element is greater than the first element. If this condition is not met, we will have to divide this array into two halves and try applying the same logic. If you do this, at some point you will arrive at a situation where you are left with only two elements or lesser. The end value is the shift index. Once the shift index is found, it is easy to find the middle element(s) for odd and even cases. Java code is below.

package dsa.arrays;

public class ShiftedSortedFindMiddle {
 
 public static void main(String[] args) {
  ShiftedSortedFindMiddle ssfm = new ShiftedSortedFindMiddle();
  ssfm.findMiddleOfArray(null);
  ssfm.findMiddleOfArray(new int[]{15,16,1,3,6,7});
  ssfm.findMiddleOfArray(new int[]{2,3,1});
  ssfm.findMiddleOfArray(new int[]{6,7,8,1,2,3,4,5});
  ssfm.findMiddleOfArray(new int[]{1,2,3,4,5});
  ssfm.findMiddleOfArray(new int[]{});
  ssfm.findMiddleOfArray(new int[]{1});
 }
  
 public void findMiddleOfArray(int[] csArray){
  if(csArray == null || csArray.length == 0) { 
   System.out.print("\nAre you Nuts? Send a valid array with at least one element you moron");
   return;
  }
  int length = csArray.length;
  int switchIndex = recursiveFind(csArray, 0 , length-1);
  System.out.print("\nMiddle Element(s) : " + csArray[(length/2 + switchIndex)%length]);
  if (length%2 == 0){
   System.out.print(" and " + csArray[(-1 + (length/2) + switchIndex)%length]);
  }
 }
 
 public int recursiveFind (int[] arr, int start, int end){
  if(end-start == 1){
   return end;
  }
  if(arr[start] > arr[end]){
   if(arr[start] > arr[end/2]){
    return recursiveFind(arr, start, end/2);
   }else if(arr[start/2] > arr[end]){
    return recursiveFind(arr, end/2 + 1, end);
   }else{
    return end;
   }
  }
  return start;
 }
 
}
/*
Are you Nuts? Send a valid array with at least one element you moron
Middle Element(s) : 7 and 6
Middle Element(s) : 2
Middle Element(s) : 5 and 4
Are you Nuts? Send a valid array with at least one element you moron
Middle Element(s) : 1
*/

Leave comments if something is unclear.

Cheers!
Braga