Write a static method that takes an array list of integers as a parameter and re

Question

Write a static method that takes an array list of integers as a parameter and returns a binary search tree composed of the array elements. The method signature is:

public static BST arrayListToBST(ArrayList<Integer> elements)

then write a static method that takes a binary search tree as a parameter and returns a sorted array list composed of the BST elements. The method signature is:

public static ArrayList<Integer> bstToSortedArrayList (BST tree)

Finally using the methods implemented above write a static method that takes any array list and returns a sorted array list. The method signature is:

public static ArrayList<Integer> arrayListToSortedArrayList(ArrayList<Integer> elements)

Explanation / Answer

package chegg;
import java.util.*;

public class BST {

/* Nested Class containing left and right child of current node and key value*/
class Node {
int val;
Node left, right;

public Node(int val_) {
val = val_;
left = right = null;
}
}

// Root of BST
Node root;

// Construct values here
BST() {
root = null;
}

// This method mainly calls insertHelper()
void insert(int val) {
root = insertHelper(root, val);
}

/* A recursive function to insert a new key in BST */
Node insertHelper(Node root, int key) {

/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}

/* Otherwise, recur down the tree with left and right childs*/
if (key < root.val)
root.left = insertHelper(root.left, key);
else if (key > root.val)
root.right = insertHelper(root.right, key);

return root;
}

ArrayList<Integer> inorder() {// Will inorderHelper here
ArrayList<Integer> a = new ArrayList<Integer>();
inorderHelper(root, a);
return a;
}

// A function to do inorder traversal of BST
void inorderHelper(Node root, ArrayList<Integer> a) {
if (root != null) {
inorderHelper(root.left, a);// visit left node
a.add(root.val);// Add to list
inorderHelper(root.right, a);// visit right node
}
}
  
public static BST getBST(ArrayList<Integer> a)
{
BST bst = new BST();
for(int val: a)
{
bst.insert(val);
}
return bst;
}

public static ArrayList<Integer> getArrayList(BST tree)
{
return tree.inorder();
}

public static ArrayList<Integer> arrayListToSortedArrayList(ArrayList<Integer> elements)
{
Collections.sort(elements);
return elements;
}
public static void main(String[] args) {
// Now let's do some testing;
// make a arraylist of numbers
ArrayList<Integer> a = new ArrayList<Integer>();
a.add(3);
a.add(1);
a.add(4);
BST tree = getBST(a);// get tree
System.out.println(getArrayList(tree));// print 1, 3, 4
System.out.println(arrayListToSortedArrayList(a));// print 1, 3, 4
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.