RishabG
BAN USERWe can find the inorder traversal of the tree and check if the data in every left node is less than (not less than or equal to) to the data in it's right node. If it is a BST then the duplicate elements will be consecutive in the inorder traversal.
This is a very simple slution. The inorder traversal can be done either using recursion or the iterative method.
This problem can be solved using the iterative method. Only a stack is needed. Here is my code for this problem and works completely fine.
class Node{
Node left, right;
int data;
Node(int x){
data=x;
}
}
public class BinaryTreeIteratorMc {
Node root;
void InOrder(){
Stack<Node> stack=new Stack<Node>();
Node n=root;
if(n==null)
return;
while(n!=null){
stack.push(n);
n=n.left;
}
while(stack.size()>0){
n=stack.pop();
System.out.print(n.data+" ");
if(n.right!=null){
n=n.right;
//System.out.println("in if");
while(n!=null){
//System.out.println("in while");
stack.add(n);
n=n.left;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTreeIteratorMc tree=new BinaryTreeIteratorMc();
tree.root=new Node(1);
tree.root.left=new Node(2);
tree.root.right=new Node(3);
tree.root.left.left=new Node(4);
tree.root.left.right=new Node(5);
tree.root.right.right=new Node(6);
System.out.println("Inorder traversal is :");
tree.InOrder();
}
}
This is my java code :
class Nodecomp{
Nodecomp left, right;
int data;
Nodecomp(int x){
data=x;
}
}
public class CompareInorder {
Nodecomp root;
boolean InOrder(Nodecomp node1, Nodecomp node2){
Stack<Nodecomp> stack=new Stack<Nodecomp>();
Stack<Nodecomp> stack2=new Stack<Nodecomp>();
Nodecomp n=node1;
Nodecomp n2=node2;
if(n==null||n2==null)
return false;
while(n!=null){
stack.push(n);
n=n.left;
}
while(n2!=null){
stack2.push(n2);
n2=n2.left;
}
while(stack.size()>0&&stack2.size()>0){
n=stack.pop();
n2=stack2.pop();
if(n.data!=n2.data){
return false;
}
if(n.right!=null){
n=n.right;
while(n!=null){
stack.add(n);
n=n.left;
}
}
if(n2.right!=null){
n2=n2.right;
while(n2!=null){
stack2.add(n2);
n2=n2.left;
}
}
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CompareInorder tree=new CompareInorder();
tree.root=new Nodecomp(1);
tree.root.left=new Nodecomp(2);
tree.root.right=new Nodecomp(3);
CompareInorder tree1=new CompareInorder();
tree1.root=new Nodecomp(2);
tree1.root.right=new Nodecomp(1);
tree1.root.right.right=new Nodecomp(3);
System.out.println("Are they equal :"+tree1.InOrder(tree.root, tree1.root));
}
}
This is my java code using arraylist. But using hashset would have a lesser time complexity.
class Nodedup{
Nodedup next;
int data;
Nodedup(int x){
data=x;
}
}
public class CircularLLDuplicate {
Nodedup root;
ArrayList<Integer> l=new ArrayList<Integer>();
boolean FindDup(Nodedup r){
Nodedup temp=r.next, start=r;
while(temp!=start){
if(l.contains(temp.data)){
return false;
}
l.add(temp.data);
temp=temp.next;
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CircularLLDuplicate link=new CircularLLDuplicate();
link.root=new Nodedup(1);
link.root.next=new Nodedup(2);
link.root.next.next=new Nodedup(3);
link.root.next.next.next=new Nodedup(4);
link.root.next.next.next.next=new Nodedup(5);
link.root.next.next.next.next=link.root;
System.out.println(link.FindDup(link.root));
}
}
This is the java code to solve this problem.
class Nodecom{
Nodecom next;
int data;
Nodecom(int x){
data=x;
}
}
public class CombineLists {
Nodecom root;
public void print(){
Nodecom temp =root;
if(temp==null)
return;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public void combine(Nodecom root1, Nodecom root2){
Nodecom l1=root1;
Nodecom l2=root2;
if(l1==null||l2==null){
System.out.println("One of the nodes is empty");
return;
}
while(l1.next!=null||l2.next!=null){
Nodecom t1=l1.next;
Nodecom t2=l2.next;
l1.next=l2;
l2.next=t1;
l1=t1;
l2=t2;
}
l1.next=l2;
l2.next=null;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CombineLists link =new CombineLists();
link.root=new Nodecom(1);
link.root.next=new Nodecom(2);
link.root.next.next=new Nodecom(3);
link.root.next.next.next=new Nodecom(4);
link.root.next.next.next.next=new Nodecom(10);
link.print();
CombineLists link2 =new CombineLists();
link2.root=new Nodecom(21);
link2.root.next=new Nodecom(22);
link2.root.next.next=new Nodecom(23);
link2.root.next.next.next=new Nodecom(24);
link2.root.next.next.next.next=new Nodecom(25);
System.out.println("2nd list is");
link2.print();
link.combine(link.root, link2.root);
System.out.println("Combined list is ");
link.print();
}
}
This is my java solution with a time complexity of O(n) :
class Nodeapp{
Nodeapp next;
int data;
Nodeapp(int x){
data=x;
}
}
public class NodeAppendN {
Nodeapp root;
public void print(){
Nodeapp temp =root;
if(temp==null)
return;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public void append(int n){
Nodeapp fast=root, slow=root;
Nodeapp temp=root;
for(int i=0;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
slow=slow.next;
fast=fast.next;
}
Nodeapp jk=slow.next;
slow.next=null;
fast.next=temp;
root=jk;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
NodeAppendN link =new NodeAppendN();
link.root=new Nodeapp(1);
link.root.next=new Nodeapp(2);
link.root.next.next=new Nodeapp(3);
link.root.next.next.next=new Nodeapp(4);
link.root.next.next.next.next=new Nodeapp(5);
link.print();
link.append(2);
System.out.println("Appended list is");
link.print();
}
}
This is my java code. It has a time complexity of O(n).
class Nodeq{
Nodeq next;
int data;
Nodeq(int x){
data=x;
}
}
public class LinkedListReverse {
Nodeq root;
public void print(){
Nodeq temp =root;
if(temp==null)
return;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public void reverse(){
Nodeq fast=root,med=root;
Nodeq slow=root;
if(fast==null)
return;
for(int i=0;i<4;i++){
med=fast;
fast=fast.next;
if(fast==null){
System.out.println("Node are less than five");
return;
}
}
while(fast.next!=null){
slow=slow.next;
med=med.next;
fast=fast.next;
//System.out.println("In fast");
}
for(int i=0;i<2;i++){
int temp=slow.data;
slow.data=fast.data;
fast.data=temp;
fast=med;
slow=slow.next;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedListReverse link=new LinkedListReverse();
link.root=new Nodeq(1);
link.root.next=new Nodeq(2);
link.root.next.next=new Nodeq(3);
link.root.next.next.next=new Nodeq(4);
link.root.next.next.next.next=new Nodeq(5);
link.root.next.next.next.next.next=new Nodeq(6);
link.root.next.next.next.next.next.next=new Nodeq(7);
link.root.next.next.next.next.next.next.next=new Nodeq(8);
link.root.next.next.next.next.next.next.next.next=new Nodeq(9);
link.print();
link.reverse();
System.out.println("Reversed link is : ");
link.print();
}
}
I am beginner in DS. This is a very simple code i wrote in java using LinkedList. I assume the numbers in the text to be separated by commas and i am returning the numbers in string type.
Can somebody please tell me if this is an appropriate method to solve this problem. Also, I am not able to figure out the time complexity of my solution.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;
public class FindIfNumberPresentFB {
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
LinkedList<String> link=new LinkedList<String>();
Scanner sc=new Scanner(new File("E:/Java/Workspace/text.txt"));
String in="";
while(sc.hasNext()){
in=in+sc.next();
}
System.out.println(in);
String ll="";
for(int i=0;i<in.length();i++){
if(in.charAt(i)==','){
link.add(ll);
ll="";
}
else{
ll+=in.charAt(i);
}
}
//System.out.println("Linkedlist is "+link);
String n="123";
int test=Integer.parseInt(n);
char f=n.charAt(0);
//System.out.println("f is "+f);
int size=n.length();
//System.out.println("size is "+size);
while(!link.isEmpty()){
String app="";
String z=link.removeFirst();
//System.out.println("z is "+z);
for(int i=0;i<10;i++){
//System.out.println("chars are "+z.charAt(i));
//System.out.println("f is "+f);
if(z.charAt(i)==f){
for(int j=i;j<i+size;j++){
// System.out.println("j is "+j);
app+=z.charAt(j);
}
//System.out.println("app is "+app);
int sample=Integer.parseInt(app);
//System.out.println("sample is "+sample);
//System.out.println("test is "+test);
if(sample==test){
//System.out.println("In if");
//System.out.println("z is "+z);
//System.out.println(z.getClass().getName());
//System.out.println("Z in int is "+Integer.parseInt(z));
//System.out.println(z.getClass().getName());
System.out.println("Number containing is "+z);
}
}
}
}
}
}
From the question I understand that the integer k need not be present in the array. Hence the solution would be to find the average of the numbers present in the array. This average would be the required number k.
- RishabG October 12, 2016