Discussion on Tree: Huffman Decoding Challenge

Sort 513 Discussions, By:

5 days ago+ 0 comments

My submission for Java 7

The main thing I was having difficulty with getting right in my pattern was skipping the root value check because it will always be null. This is because I was going to check the value of ever node in the Binary Tree before moving onto the next one. By doing the reverse and then checking if the current Node had no children, the pattern could operate correctly to what the problem desired.

void decode(String s, Node root) {
        Node currNode = root;
        for (int i = 0; i < s.length(); i++) {
            //root node will always be null
            if (s.charAt(i) == '0') {
                currNode = currNode.left;
            } else if (s.charAt(i) == '1') {
                currNode = currNode.right;
            }
            
            if (currNode.left == null && currNode.right == null) {
                System.out.print(currNode.data);
                currNode = root;
            }
        }
    } // decode end

1 week ago+ 1 comment

Questions is broken in C. In test cases, input is string and output is same string as input. Also, no funcion definition "decode_huff" exists to "complete" because code editor is just an empty main().

100% credit with simple scanf(), printf().

1 week ago+ 0 comments

Simple python tree traversal O(N)

from collections import deque
# Enter your code here. Read input from STDIN. Print output to STDOUT
def decodeHuff(root, s):
	#Enter Your Code Here
    code = deque(s)
    curr_node = root
    return_list = []
    while code:
        curr_code = code.popleft()
        if curr_code == '0':
            curr_node = curr_node.left
        else:
            curr_node = curr_node.right
        
        if curr_node.data != "\x00":
            return_list.append(curr_node.data)
            curr_node = root
    
    print("".join(return_list))

3 weeks ago+ 0 comments

Done in Java.

void decode2(String s, Node node, Node root) {
   if(s.length()>0){
      char bit = s.charAt(0);
      String snext = ""; 
      if(s.length()>1){
            snext = s.substring(1, s.length());    
      }

      if(node.right == null && node.left == null){
            System.out.print(node.data);
            if(bit=='0'){
            decode2(snext, root.left, root);
            } else if(bit=='1'){
            decode2(snext, root.right, root);
            }
      } else {
            if(bit=='0'){
            decode2(snext, node.left, root);
            } else if(bit=='1'){
            decode2(snext, node.right, root);
            }
      }
      } else {
      System.out.print(node.data);
      }

}

void decode(String s, Node root) {
      decode2(s,root,root);
}

3 weeks ago+ 0 comments

Python

Used the fact that the nodes containing phi in the example have the ord() equal to 0 which allowed me to pass it to ord(). I didn't think about the fact that both the left and right branches would be empty as shown on many other examples.

def decodeHuff(root, s):
    idx = 0
    ans = []
    current = root
    while idx < len(s):
        if s[idx] == '1':
            current = current.right
            idx += 1
        else:
            current = current.left
            idx += 1
        if ord(current.data) != 0:
            ans.append(current.data)
            current = root
    
    final = ''.join(ans)
    print(final)

Load more conversations