Given an array that represents Breadth First Search or BFS traversal of a Complete Binary Search Tree, implement a recursive void method to print the preOrder traversal of the same Complete Binary Search Tree. You do not need to construct the BST. A Complete Binary Search Tree is a BST in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Following is an example of a Complete Binary Search Tree: A. BFS traversal array (level by level from left to right): bfs[] = {50, 35, 55, 30, 45} B. PreOrder traversal (middle, left, right) : 50 35 30 45 55 Your recursive method "void convertBFStoPreOrder" will get an array A as an input and will print B. Hints: In the given BFS traversal array, bfs[], if i is the index of a parent, 2i+1 will give you the index of the left child, and 2i+2 will give you the index of the right child. "Assume that input array is always correct and represent a correct BFS traversal of a Complete BST." ------------------------------------------------------------------------------------------------ Sample input1: 5 50 35 55 30 45 Sample output1: 50 35 30 45 55 ------------------------------------------------------------------------------ Sample input2: 13 45 35 55 25 40 50 60 20 27 37 43 47 54 Sample output2: 45 35 25 20 27 40 37 43 55 50 47 54 60 ---------------------------
Given an array that represents Breadth First Search or BFS traversal of a Complete Binary Search Tree, implement a recursive void method to print the preOrder traversal of the same Complete Binary Search Tree. You do not need to construct the BST.
A Complete Binary Search Tree is a BST in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Following is an example of a Complete Binary Search Tree:
A. BFS traversal array (level by level from left to right): bfs[] = {50, 35, 55, 30, 45}
B. PreOrder traversal (middle, left, right) : 50 35 30 45 55
Your recursive method "void convertBFStoPreOrder" will get an array A as an input and will print B.
Hints:
In the given BFS traversal array, bfs[], if i is the index of a parent, 2i+1 will give you the index of the left child, and 2i+2 will give you the index of the right child.
"Assume that input array is always correct and represent a correct BFS traversal of a Complete BST."
------------------------------------------------------------------------------------------------
Sample input1:
5
50 35 55 30 45
Sample output1:
50 35 30 45 55
------------------------------------------------------------------------------
Sample input2:
13
45 35 55 25 40 50 60 20 27 37 43 47 54
Sample output2:
45 35 25 20 27 40 37 43 55 50 47 54 60
---------------------------
![DriverMain.java
ProblemSolution.java ® entrypoint.z
1• import java.util.*;
2 import java.lang.*;
3 import java.io.*;
4 //Your program will be evaluated by this DriverMain class and several test cases.
5
6 - public class DriverMain {
public static void main(String[] args) {
Scanner s = new Scanner (System.in);
7
8
int N = s.nextInt();
int A[]
9
= new int[N];
for (int i = 0; i < N; i++) {
10
11 .
12
A[i] = s.nextInt();
13
}
14
ProblemSolution problemSolution = new ProblemSolution();
15
problemSolution.solution(A, N);
16
}
17 }](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe7d091e4-db60-4419-a20a-855eb5ec8036%2F5e3b22ca-9a63-4dcb-950e-7da45313abba%2F5d8tfol_processed.png&w=3840&q=75)
![DriverMain.java
ProblemSolution.java
entrypoint.cz
1- import java.util.*;
2 import java.lang.*;
3 import java.io.*;
4 v public class ProblemSolution {
5
public void solution(int[] bfs, int N) {
6
//write your recursive code here to convert bfs to preorder traversal of a complete
7
//You can add new methods
8
9
10
11 }
12 }
13](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe7d091e4-db60-4419-a20a-855eb5ec8036%2F5e3b22ca-9a63-4dcb-950e-7da45313abba%2Fhf13y6j_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
