I was looking at the code challenge from gfg BST to max heap:
Given a Binary Search Tree. Convert a given BST into a Special Max Heap with the condition that all the values in the left subtree of a node should be less than all the values in the right subtree of the node. This condition is applied on all the nodes in the so converted Max Heap.
I could not solve the challenge.
So I had a look at the following solution code:
class Solution
{
public static ArrayList<Integer> list=new ArrayList<>();
static int i=0;
public static void InOrderTraversal(Node root){
if(root == null) return ;
InOrderTraversal(root.left);
list.add(root.data);
InOrderTraversal(root.right);
}
public static void PostOrderTraversal(Node root){
if(root == null )return;
PostOrderTraversal(root.left);
PostOrderTraversal(root.right);
root.data= list.get(i);
i++;
}
public static void convertToMaxHeapUtil(Node root)
{
InOrderTraversal(root);
PostOrderTraversal(root);
}
}
I don't see how this code could change the structure of the tree, as it neither adds nor deletes any nodes. Here is the second sample testcase copied from gfg official website:
Input BST:
3
/ \
1 5
\ / \
2 4 6
\
7
Expected Max heap output:
7
/ \
3 6
/ \ / \
1 2 4 5
I can't understand how it is working on that test case.
Driver code for the problem:
//{ Driver Code Starts
//Initial Template for Java
import java.util.LinkedList;
import java.util.Queue;
import java.io.*;
import java.util.*;
class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left=null;
right=null;
}
}
class Tree {
static Node buildTree(String str){
if(str.length()==0 || str.charAt(0)=='N'){
return null;
}
String ip[] = str.split(" ");
// Create the root of the tree
Node root = new Node(Integer.parseInt(ip[0]));
// Push the root to the queue
Queue<Node> queue = new LinkedList<>();
queue.add(root);
// Starting from the second element
int i = 1;
while(queue.size()>0 && i < ip.length) {
// Get and remove the front of the queue
Node currNode = queue.peek();
queue.remove();
// Get the current node's value from the string
String currVal = ip[i];
// If the left child is not null
if(!currVal.equals("N")) {
// Create the left child for the current node
currNode.left = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.left);
}
// For the right child
i++;
if(i >= ip.length)
break;
currVal = ip[i];
// If the right child is not null
if(!currVal.equals("N")) {
// Create the right child for the current node
currNode.right = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.right);
}
i++;
}
return root;
}
static void postOrder(Node root)
{
if(root == null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+" ");
}
public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
while(t > 0){
String s = br.readLine();
Node root = buildTree(s);
Solution g = new Solution();
g.convertToMaxHeapUtil(root);
postOrder(root);
System.out.println();
t--;
}
}
}
// } Driver Code Ends