In: Computer Science
Huffman codes T/F Questions:
Q1 : Let s be the depth of the leaf with the smallest depth (i.e. closest to the root) in an optimal prefix-free code tree T. Then the highest frequency character has depth s in T. (Assume frequencies are distinct.) T or F
Q2 : Let T be an optimal prefix-free code tree, and let v be any non-leaf node in T. If we exchange the left and right subtrees of v (i.e. swap its left and right child pointers) then the resulting new tree must still be an optimal prefix-free code tree. T or F
Please explain why it's either T or F
Solution:
(1)
The answer wil be "T"
Explanation:
=>If all the characters have district frequencies then while drawing Huffman's tree we first choose 2 smallest frequent characters then move in the higher level of tree depending upon the frequencies of characters in increasing order.
=>As s is the depth of the leaf node and it is also smallest means it is very close to the root node then we can say that it will be the most frequent character as most frequent character lie in the highest level of Huffman's tree.
=>Hence on the basis of above statements we can say that given statement is true.
(2)
The answer will be "T"
Explanation:
=>Given that T is optimal prefix free code tree so there will be left and right child for every non leaf node.
=>If we change/swap left and right nodes of some node v then in that case codewords of all the characters will not be prefix of any other means will be prefix free code because we are just swapping the locations and it will not repeat any prefix codeword.
=>Hence on the basis of above statements we can say that given statement is true.
I have explaind each and every part with the help of statements attached to it.