How to traverse tree for making binary code from a HuffmanTree?

Question

I'm trying to make binary code from a Huffman tree. I am stuck at tree traversal. To traverse tree and print code for every character frequency, I've written following code.

def printCode(node,prefix=""):
    if node.left:
        prefix = prefix+"0"
        printCode(node.left,prefix)
    elif node.right:
        prefix = prefix+"1"
        printCode(node.right,prefix)
    elif node.internal ==False:
        print(node.data,prefix)
        printCode(node,prefix="") #need change

Here is the necessary explanation: If a node is not an internal node(node.internal=False) then it is a leaf, and at this point of traversal I'm printing the code with character frequencies. But i'm unable to go back to the previous internal node and continue with another branch of tree that has not been traversed yet. So this code is ended with only returning binary code for the first leaf of the tree.

The every node of tree is created with following code:

class Node:
    def __init__(self,data,internal=False):
        self.data = data  #frequency of a char
        self.internal = internal

        self.left = None
        self.right = None

@SPYBUG96 if node.internal == True then it is a leaf, and at this point i'm gonna print the code for this leaf. I want to print leaves and corresponding binary code. — exiled

SPYBUG96 SPYBUG96 · Accepted Answer · 2018-12-13T16:41:57

The main problem with your logic is the use of the elif

def printCode(node):
    if node.left:
        node.left.prefix = node.prefix+"0"
        printCode(node.left)

    if node.right:
        node.right.prefix = node.prefix+"1"
        printCode(node.right)

    if node.internal == False:
        print(node.data,node.prefix)

This way it will traverse the left side of the tree until it reaches a leaf, when it reaches a leaf it will print the node data. At this point in the code it goes back to the last recursive call (the node before the leaf) and it will go to the right node, if this right node is a leaf it will print out its node information, then it will go back to the last recursive call

Let me know if you need a better explanation, or if there was a misunderstanding and this doesn't do what you want it to

UPDATE:

class Node:
    def __init__(self,data,internal=False):
        self.data = data  #frequency of a char
        self.internal = internal

        self.left = None
        self.right = None

        #Add a prefix to your nodes, so each node keeps track of its own prefix
        self.prefix = ""

How to traverse tree for making binary code from a HuffmanTree?

1 Answers