import java.io.*;

import java.util.*;

class BTNode{

private int nodeid;

private int data;

private int levelNum;

private BTNode leftChildPtr;

private BTNode rightChildPtr;

public BTNode(){}

public void setNodeId(int id){

nodeid = id;

}

public int getNodeId(){

return nodeid;

}

public void setData(int d){

data = d;

}

public int getData(){

return data;

}

public void setLevelNum(int level){

levelNum = level;

}

public int getLevelNum(){

return levelNum;

}

public void setLeftChildPtr(BTNode ptr){

leftChildPtr = ptr;

}

public void setRightChildPtr(BTNode ptr){

rightChildPtr = ptr;

}

public BTNode getLeftChildPtr(){

return leftChildPtr;

}

public BTNode getRightChildPtr(){

return rightChildPtr;

}

public int getLeftChildID(){

if (leftChildPtr == null)

return -1;

return leftChildPtr.getNodeId();

}

public int getRightChildID(){

if (rightChildPtr == null)

return -1;

return rightChildPtr.getNodeId();

}

}

class BinarySearchTree{

private int numNodes;

private BTNode[] arrayOfBTNodes;

private int rootNodeID;

public BinarySearchTree(int n){

numNodes = n;

arrayOfBTNodes = new BTNode[numNodes];

for (int index = 0; index

arrayOfBTNodes[index] = new BTNode();

arrayOfBTNodes[index].setNodeId(index);

arrayOfBTNodes[index].setLeftChildPtr(null);

arrayOfBTNodes[index].setRightChildPtr(null);

arrayOfBTNodes[index].setLevelNum(-1);

}

}

public void setLeftLink(int upstreamNodeID, int downstreamNodeID){

arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(arrayOfBTNodes[downstreamNodeID]);

}

public void setRightLink(int upstreamNodeID, int downstreamNodeID){

arrayOfBTNodes[upstreamNodeID].setRightChildPtr(arrayOfBTNodes[downstreamNodeID]);

}

public void selectionSort(int array[], int arraySize){

for (int iterationNum = 0; iterationNum

int minIndex = iterationNum;

for (int j = iterationNum+1; j

if (array[j]

minIndex = j;

}

// swap array[minIndex] with array[iterationNum]

int temp = array[minIndex];

array[minIndex] = array[iterationNum];

array[iterationNum] = temp;

}

}

public void constructBSTree(int[] array){

int leftIndex = 0;

int rightIndex = numNodes-1;

int middleIndex = (leftIndex + rightIndex)/2;

rootNodeID = middleIndex;

arrayOfBTNodes[middleIndex].setData(array[middleIndex]);

ChainNodes(array, middleIndex, leftIndex, rightIndex);

}

public void ChainNodes(int[] array, int middleIndex, int leftIndex, int rightIndex){

if (leftIndex

int rootIDLeftSubtree = (leftIndex + middleIndex-1)/2;

setLeftLink(middleIndex, rootIDLeftSubtree);

arrayOfBTNodes[rootIDLeftSubtree].setData(array[rootIDLeftSubtree]);

ChainNodes(array, rootIDLeftSubtree, leftIndex, middleIndex-1);

}

if (rightIndex > middleIndex){

int rootIDRightSubtree = (rightIndex + middleIndex + 1)/2;

setRightLink(middleIndex, rootIDRightSubtree);

arrayOfBTNodes[rootIDRightSubtree].setData(array[rootIDRightSubtree]);

ChainNodes(array, rootIDRightSubtree, middleIndex+1, rightIndex);

}

}

public void printLeafNodes(){

for (int id = 0; id

if (arrayOfBTNodes[id].getLeftChildPtr() == null && arrayOfBTNodes[id].getRightChildPtr() == null)

System.out.print(arrayOfBTNodes[id].getData() + " ");

}

System.out.println();

}

public void InOrderTraversal(int nodeid){

if (nodeid == -1)

return;

InOrderTraversal(arrayOfBTNodes[nodeid].getLeftChildID());

System.out.print(arrayOfBTNodes[nodeid].getData() + " ");

InOrderTraversal(arrayOfBTNodes[nodeid].getRightChildID());

}

public void PrintInOrderTraversal(){

InOrderTraversal(rootNodeID);

System.out.println();

}

}

class BSTRandomArraySortedInputs{

public static void selectionSort(int array[], int arraySize){

for (int iterationNum = 0; iterationNum

int minIndex = iterationNum;

for (int j = iterationNum+1; j

if (array[j]

minIndex = j;

}

// swap array[minIndex] with array[iterationNum]

int temp = array[minIndex];

array[minIndex] = array[iterationNum];

array[iterationNum] = temp;

}

}

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int numElements;

System.out.print("Enter the number of elements: ");

numElements = input.nextInt();

int array[] = new int[numElements];

int maxValue;

System.out.print("Enter the maximum value for an element: ");

maxValue = input.nextInt();

Random randGen = new Random(System.currentTimeMillis());

System.out.print("Array Generated: ");

for (int index = 0; index

array[index] = randGen.nextInt(maxValue);

System.out.print(array[index] +" ");

}

System.out.println();

selectionSort(array, numElements);

BinarySearchTree bsTree = new BinarySearchTree(numElements);

bsTree.constructBSTree(array);

System.out.println("Inorder Traversal: ");

bsTree.PrintInOrderTraversal();

System.out.print("Leaf nodes: ");

bsTree.printLeafNodes();

System.out.println();

}

}

C filci/C:Userz/J00736238/DownloadaKSC226-Fall2017.proiect-9. BST pdf CSC 228 Data Structures and Algorithims, Fall 2017 Project 9: Binary Search Tree: Lawest Common Ancestor Node Due: November 17 1 Psubmission through Canvas) The lowed cummon ancestor LCA) for two moxios A and B in a binary sarh tro (BST) is th: noke thal is the common ancestor for both A and B, and is th arthest away from the ruot node of the BST. Note that depending on the EST, one of the tw nodes A and B could themselves be the LCA o the ther node or a third node that is different from nodes and B> could be the LCA. The three cases are illustrated in the following figare: 21 21 21 78 TE 25) (81 1224) (34 122434 24 Node Node Nod3' with cata 21 4 and 2 spatively In this project, you will construct a BST based oa a randomly generated and sorted anmy ot integers input the valuese., data) tor two nodes A and B (that are pat of the HS1) and find the ata corresponding to their LUA. Pol kw the steps bekoa (1) Yo will fiest cons& BST using a randomly gemerated and sceted array(sorta using Seleclioen soN) The code tooct such a RST is givs no y. (2) You will th iu he lvalues for the uscarch nokes A and R. Retween the Iwo les, node will be then called the rightSearchNode. 3 The thind and the major step is to initiate a search process starting from the root node icalled say, the If the data toe the lensearcNode and rightserchNode are hoch lower than thar od the o nodes should he loeared in th Hacs wese the id o thepepactive ancestor ede tacoeond oe id of its left child and CIMtinie the rch preless in is lefl sal, Ira. prospectiveAcestorNode, then the two nodes should be in the right sub tree of the ts night child and crine the search process in its right sub tree If the data for the leiSearchNode and righiSearchNode are boch reater than that oe the t. Hence, we set the id the pcospective ancestor node to correspond to the id ot Iype here to search C filci/C:Userz/J00736238/DownloadaKSC226-Fall2017.proiect-9. BST pdf CSC 228 Data Structures and Algorithims, Fall 2017 Project 9: Binary Search Tree: Lawest Common Ancestor Node Due: November 17 1 Psubmission through Canvas) The lowed cummon ancestor LCA) for two moxios A and B in a binary sarh tro (BST) is th: noke thal is the common ancestor for both A and B, and is th arthest away from the ruot node of the BST. Note that depending on the EST, one of the tw nodes A and B could themselves be the LCA o the ther node or a third node that is different from nodes and B> could be the LCA. The three cases are illustrated in the following figare: 21 21 21 78 TE 25) (81 1224) (34 122434 24 Node Node Nod3' with cata 21 4 and 2 spatively In this project, you will construct a BST based oa a randomly generated and sorted anmy ot integers input the valuese., data) tor two nodes A and B (that are pat of the HS1) and find the ata corresponding to their LUA. Pol kw the steps bekoa (1) Yo will fiest cons& BST using a randomly gemerated and sceted array(sorta using Seleclioen soN) The code tooct such a RST is givs no y. (2) You will th iu he lvalues for the uscarch nokes A and R. Retween the Iwo les, node will be then called the rightSearchNode. 3 The thind and the major step is to initiate a search process starting from the root node icalled say, the If the data toe the lensearcNode and rightserchNode are hoch lower than thar od the o nodes should he loeared in th Hacs wese the id o thepepactive ancestor ede tacoeond oe id of its left child and CIMtinie the rch preless in is lefl sal, Ira. prospectiveAcestorNode, then the two nodes should be in the right sub tree of the ts night child and crine the search process in its right sub tree If the data for the leiSearchNode and righiSearchNode are boch reater than that oe the t. Hence, we set the id the pcospective ancestor node to correspond to the id ot Iype here to search