Calculate the time complexity of the below program and show all your work how you arrived at your result: package com.sample; import java.io.BufferedReader; import java.io.FileReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Tree { public static class TreeNode { TreeNode(int data) { this.data = data; } TreeNode leftChild; TreeNode rightChild; int data; boolean visited; } static TreeNode populateTree(String filePath) { TreeNode root = null; try { BufferedReader br = new BufferedReader(new FileReader(filePath)); String line = ""; while ((line = br.readLine()) != null) { line = line.trim(); if (line.equals("*")) { return root; } String[] nodes = line.split(","); int currentRootElement = Integer.parseInt(nodes[0]); int value = Integer.parseInt(nodes[1]); if (root == null) { root = new TreeNode(currentRootElement); root.leftChild = new TreeNode(value); } else { insertNode(root, currentRootElement, value); } } } catch (Exception e) { System.out.println("Something went wrong : " + e.getMessage()); } return root; } static void insertNode(TreeNode node, int parentElement, int currentElement) { if (node == null) return; insertNode(node.leftChild, parentElement, currentElement); if (node.data == parentElement) { if (node.leftChild == null) { node.leftChild = new TreeNode(currentElement); } else { node.rightChild = new TreeNode(currentElement); } } insertNode(node.rightChild, parentElement, currentElement); } static void searchNode(TreeNode root, String filePath) { try { BufferedReader br = new BufferedReader(new FileReader(filePath)); String line = ""; boolean isStar = false; while ((line = br.readLine()) != null) { line = line.trim(); if (line.equals("#")) { return; } if (line.equals("*")) { isStar = true; } if (!line.equals("*") && isStar) { int nodeToSearch = Integer.parseInt(line); boolean foundinDFS = DFS(root,nodeToSearch); if (foundinDFS) { System.out.println("Node " + nodeToSearch + " Successfuly Found using DFS."); } else { System.out.println("Node " + nodeToSearch + " Failed to find using DFS."); } boolean foundinBFS = BFS(root,nodeToSearch); if (foundinBFS) { System.out.println("Node " + nodeToSearch + " Successfuly Found using BFS."); } else { System.out.println("Node " + nodeToSearch + " Failed to find using BFS."); } } } } catch (Exception e) { System.out.println("Something went wrong : " + e.getMessage()); } } private static boolean DFS(TreeNode root,int nodeToSearch) { Stack s = new Stack(); s.push(root); while(!s.isEmpty()) { TreeNode node = s.pop(); if(node.data == nodeToSearch) { return true; } if(node.leftChild != null) { s.push(node.leftChild); } if(node.rightChild != null) { s.push(node.rightChild); } } return false; } private static boolean BFS(TreeNode root,int nodeToSearch) { Queue q = new LinkedList(); q.add(root); while(!q.isEmpty()) { TreeNode node=q.poll(); if(node.data == nodeToSearch) { return true; } if(node.leftChild != null) { q.add(node.leftChild); } if(node.rightChild != null) { q.add(node.rightChild); } } return false; } public static void main(String[] args) { String filePath = "C:/Users/kruthi/Desktop/Input.txt"; TreeNode root = populateTree(filePath); searchNode(root,filePath); System.out.println("Thank you!");
-->Calculate the time complexity of the below program and show all your work how you arrived at your result:
package com.sample;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Tree {
public static class TreeNode {
TreeNode(int data) {
this.data = data;
}
TreeNode leftChild;
TreeNode rightChild;
int data;
boolean visited;
}
static TreeNode populateTree(String filePath) {
TreeNode root = null;
try {
BufferedReader br = new BufferedReader(new FileReader(filePath));
String line = "";
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.equals("*")) {
return root;
}
String[] nodes = line.split(",");
int currentRootElement = Integer.parseInt(nodes[0]);
int value = Integer.parseInt(nodes[1]);
if (root == null) {
root = new TreeNode(currentRootElement);
root.leftChild = new TreeNode(value);
}
else {
insertNode(root, currentRootElement, value);
}
}
}
catch (Exception e) {
System.out.println("Something went wrong : " + e.getMessage());
}
return root;
}
static void insertNode(TreeNode node, int parentElement, int currentElement) {
if (node == null)
return;
insertNode(node.leftChild, parentElement, currentElement);
if (node.data == parentElement) {
if (node.leftChild == null) {
node.leftChild = new TreeNode(currentElement);
}
else {
node.rightChild = new TreeNode(currentElement);
}
}
insertNode(node.rightChild, parentElement, currentElement);
}
static void searchNode(TreeNode root, String filePath) {
try {
BufferedReader br = new BufferedReader(new FileReader(filePath));
String line = "";
boolean isStar = false;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.equals("#")) {
return;
}
if (line.equals("*")) {
isStar = true;
}
if (!line.equals("*") && isStar) {
int nodeToSearch = Integer.parseInt(line);
boolean foundinDFS = DFS(root,nodeToSearch);
if (foundinDFS) {
System.out.println("Node " + nodeToSearch + " Successfuly Found using DFS.");
} else {
System.out.println("Node " + nodeToSearch + " Failed to find using DFS.");
}
boolean foundinBFS = BFS(root,nodeToSearch);
if (foundinBFS) {
System.out.println("Node " + nodeToSearch + " Successfuly Found using BFS.");
} else {
System.out.println("Node " + nodeToSearch + " Failed to find using BFS.");
}
}
}
} catch (Exception e) {
System.out.println("Something went wrong : " + e.getMessage());
}
}
private static boolean DFS(TreeNode root,int nodeToSearch) {
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while(!s.isEmpty()) {
TreeNode node = s.pop();
if(node.data == nodeToSearch) {
return true;
}
if(node.leftChild != null) {
s.push(node.leftChild);
}
if(node.rightChild != null) {
s.push(node.rightChild);
}
}
return false;
}
private static boolean BFS(TreeNode root,int nodeToSearch) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
while(!q.isEmpty()) {
TreeNode node=q.poll();
if(node.data == nodeToSearch) {
return true;
}
if(node.leftChild != null) {
q.add(node.leftChild);
}
if(node.rightChild != null) {
q.add(node.rightChild);
}
}
return false;
}
public static void main(String[] args) {
String filePath = "C:/Users/kruthi/Desktop/Input.txt";
TreeNode root = populateTree(filePath);
searchNode(root,filePath);
System.out.println("Thank you!");
}
}
Step by step
Solved in 2 steps
