Question

This is binary search tree problem. The program reads the text file, and creates a binary search tree based on the words in the file.

I can create the tree but I also have to store 'the order of insertion' in each node.  

For example, if text includes "the" 3 times and it is the 1st, 5th, and 9th word in the file,

in binary search tree, one node should have string value "the" and array list{1, 5, 9}.

How can I implement this array list part in Java?

Answer 1

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class BinarySearchTree
{
  
static class Node {
String key;
Node left, right;
ArrayList<Integer>l;
};
Node root;
public BinarySearchTree() {
   root=null;
}
  
Node newNode(String data,int pos)
{
Node temp = new Node();
  
temp.key = data;
  
temp.left = null;
temp.right = null;
temp.l=new ArrayList<>();
temp.l.add(pos);
return temp;
}
  

void insert(String key,int pos) {
root = insertRec(root, key,pos);
}

Node insertRec(Node root, String key,int pos) {

if (root == null) {
root = newNode(key, pos);
return root;
}

if (key.compareTo(root.key)<0)
root.left = insertRec(root.left, key,pos);
else if (key.compareTo(root.key)>0)
root.right = insertRec(root.right, key,pos);
else {
   root.l.add(pos);
}

return root;
}   

void Inorder(Node root)
{
if (root == null)
return;
else {
Inorder(root.left);
System.out.print( root.key +" ");
for(int i=0;i<root.l.size();i++) {
   System.out.print(root.l.get(i)+" ");
}
System.out.println();
Inorder(root.right);
}
}

public static void main(String args[]) throws IOException
{
BinarySearchTree b=new BinarySearchTree();
int count=1;
File file = new File("C:\\Users\\Administrator\\Desktop\\demo.txt");
  
BufferedReader br = new BufferedReader(new FileReader(file));
  
String st;
while ((st = br.readLine()) != null) {
  
String ss[]=st.split(" ");
for(int i=0;i<ss.length;i++) {
   b.insert(ss[i],count);
   count++;
}
}
b.Inorder(b.root);
  
}
}

// please give thumbs-up for it....Happy Coding!