Tuesday, June 9, 2015

Google : Same Inorder of BST

package binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class Tree<T> {
 Node<T> root;
 
 public Tree(){
  
 }
 public Node<T> getRoot(){
  return root;
 }
 public void setRoot(T data){
  root = new Node<T>();
  root.setData(data);
 }
 
 public void addLeftChild(T par, T chld){
  Node<T> parNode = getNode(par);
  if(parNode != null){
   Node<T> leftNode = parNode.getLeft();
   if(leftNode == null){
    leftNode = new Node<T>();
    parNode.setLeft(leftNode);
   }
   leftNode.setData(chld);
  }
 }
 
 public void addRightChild(T par, T chld){
  Node<T> parNode = getNode(par);
  if(parNode != null){
   Node<T> rightNode = parNode.getRight();
   if(rightNode == null){
    rightNode = new Node<T>();
    parNode.setRight(rightNode);
   }
   rightNode.setData(chld);
  }
 }
 
 public Node<T> getNode(T data){
  return getNode(getRoot(), data);
 }
 public Node<T> getNode(Node<T> node, T data){
  if(node != null){
   if(node.getData().equals(data)){
    return node;
   }
   Node<T> leftNodeResult = getNode(node.getLeft(),data);
   if(leftNodeResult != null){
    return leftNodeResult;
   }
   Node<T> rightNodeResult = getNode(node.getRight(),data);
   if(rightNodeResult != null){
    return rightNodeResult;
   }
  }
  return null;
 }
 
 public void inOrder(Node<T> node,List<T> list){
  if(node != null){
   if(node.getLeft() != null){
    inOrder(node.getLeft(),list);
   }
   list.add(node.getData());
   if(node.getRight() != null){
    inOrder(node.getRight(),list);
   }
  }
 }
 
 public List<T> inOrder(){
  List<T> list = new ArrayList<T>();
  inOrder(root,list);
  return list;
 }
 
 public boolean isSameInorder(Tree<T> other){
  Iterator<T> thisListIter = inOrder().iterator();
  Iterator<T> otherListIter = other.inOrder().iterator();
  while(thisListIter.hasNext() && otherListIter.hasNext()){
   if (thisListIter.next() != otherListIter.next()){
    return false;
   }
  }
  if(thisListIter.hasNext() || otherListIter.hasNext()){
   return false;
  }
  return true;
 }
}

No comments:

Post a Comment