I think it should be O(1). Huffman Coding uses Min-heap and heapsort. Heapsort has O(1) space complexity. We don't include the space required to store the input in Space Complexity.

Max-Heapify uses tail recursion because function call is at the end. Due to this tail recursion , it minimizes the space complexity of heap-sort to O(1).

So, Space Complexity of Heap-Sort is O(1).

To understand , how space complexity becomes O(1) using tail-recursion .

watch this video and then apply max-heapify algorithm for the below example and observe the space complexity using stack method.

Thank you for such a detailed explanation. I understood the concept but what about Huffman coding's space complexity? Is it O(n) or O(1). According to my understanding, we need n extra space to keep track of frequencies of the characters. What is your opinion on that.

I have given the link of University of Texas where it is mentioned that :-

We often speak of "extra" memory needed, not counting the memory needed to store the input itself.

So, we should not have to consider the input size to find the space complexity of an algorithm.

@Akash ,it should be O(n) which you have already mentioned because we have to store frequencies of characters from the input file seperately in the array.

To obtain Huffman coding we use data structure called min heap. At the initial phase all the nodes has to be present in heap(satisfying min-heap property).

If there are n elements in tree then space complexity will be O(n) which is extra space required.