Pages

Tuesday, October 21, 2014

Inorder Traversal of two binary trees

Problem Description:
Write a program to print inorder traversal of two trees.  Both values must be printed alternatively. 

e.g. if inorder traversal of tree 1 is 10, 15, 20 and tree 2 is 100, 150, 200 then it should print  10, 100, 15, 150, 20, 200. 

Solution:
I used threads to keep track of printing one by one thread, it uses recursive inorder traversal synchronized block. 

Assumptions: 
Tree need not to be same level - meaning both tree can hold different number of nodes and can differ in number of levels.




package com.java;
import java.io.Serializable;

Node.java
public class Node {
 
 public int data;
 public Node left;
 public Node right;
 
 public Node(int data, Node left, Node right) {
  super();
  this.data = data;
  this.left = left;
  this.right = right;
 }
 
 public Node(int data) {
  this(data, null, null);
 }

  public Node() {
  super();
 }
}

public static void main(String[] args) {
  
 Thread t1 = new Thread() {
  public void run() {
   TreeCheck tc = new TreeCheck();
   Node tree1 = new Node(20, new Node(10), new Node(40, new Node(30), null));
   tc.inOrder(tree1);
  }
 };
 Thread t2 = new Thread() {
  public void run() {
    TreeCheck tc = new TreeCheck();
    Node tree2 = new Node(80, new Node(60, new Node(50), new Node(70)), new Node(86, new Node(82), new Node(90)));
    tc.inOrder(tree2);
  }
 };
 
 t1.start();
 t2.start();
  
 }
 
 public void inOrder(Node root) {
  
  if(root.left != null){
   inOrder(root.left);
  }
  
  synchronized(this) {
   System.out.println(root.data);
   try {
    Thread.sleep(2000);
   } catch(Exception e) {
    e.printStackTrace();
   }
  }
  
  if(root.right != null){
   inOrder(root.right);
  }
 }
}

No comments:

Post a Comment