Tuesday, December 13, 2011

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

3 comments:

getting heat said...

Hi Braga

I'm getting below errors by compiling all three files :

The method add(Component) in the type Container is not applicable for the arguments (BinaryTreeView) PreOrderInOrderReconstructor.java
The method getWidth() is undefined for the type BinaryTreeView BinaryTreeView.java
The method paint(Graphics) is undefined for the type Object BinaryTreeView.java

BragBoy said...

@getting heat: Did you extend the JPanel and did the necessary imports?

If you notice closely, BinaryTreeView extends JPanel.

ips.jolly said...

i have given this tutorial http://bloggerplugnplay.blogspot.in/2012/11/construction-of-binary-tree-from.html