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

CodePudding user response：

The code you have presented solves this problem with the knowledge that the output tree does not need to be a complete binary tree. Although the example output show a complete binary tree as output, this is not part of the requirement of the code challenge. The automated tests will only verify that the tree in the output has all the children nodes having lesser values than their parent nodes. It does not verify the shape of the tree.

The author of this solution had the insight to just keep the shape of the tree unchanged, with all its nodes staying where they are, and only move around values in that tree.

The approach to do this is simple: first the values (not the nodes!) are collected in a list with an in-order traversal. Since it is given that the input tree is a BST, the list will get the values in sorted order.

Then the values in that list are each assigned back to the node's data, overwriting their previous values. This time the nodes are visited in post-order, which means that parent nodes will get their values later than their child nodes will get them. Since the list is sorted, this means parent nodes will get greater values than their children have. This is exactly what the test suite will test.

We do note that this solves the challenge in maybe a surprising way, but it is not something you would want to do in practice, as a heap does not provide the expected efficiency if it is not balanced.

So if you had been trying to build a solution where you would get an efficient heap as output, then I can only praise that effort. This is what the goal should be of a programmer building a heap, and it shows why solving code challenges is not always helping one to improve on solving real life coding problems.