You can do without the use of StringBuilder - simply System.out.print(c.data) instead of sb.append(c.data) in the middle of the if statement.

You could have done if(c.data!='\0') instead of checking its left and right node.

Nice! I think, instead of finding string length, we can use already present root.frequency as well. That should work as well.

you don't need to check that both left and right are null. This is a property of Huffman codes.

I am thinking out aloud, so please feel free to correct me. :)

I have two questions based on particular scenarios:

1. Assume we have a very large tree(say a billion leaves, or more) and a very large input string, will we not be traversing the tree from the root to leaf during every iteration(especially assuming the code of every leaf is present in the input string)?

2. If the input string contains codes for every leaf in the tree repeated "N" times, traversal from the root to a particular leaf would increase by a factor of N. Would this not be inefficient(especially considering 1)?

I am not sure how realistic these scenarios are but worth thinking about.

One way to increase the performace is to store the length of the string in a variable

int length = s.length();
for (int i = 0; i < length; i++)

Because in your code you are running the method length() n times * m the length of the array. Is a small comment...

void decode(String S ,Node root) { if (root == null) return; Node n = root; for (char c : S.toCharArray()){ n = c == '0' ? n.left : n.right; if (n.data != '\0'){ System.out.print(n.data+""); n = root; } }
}

Almost the same as my code.

void decode(String encoding, Node root) {
    StringBuilder result = new StringBuilder();
    Node curr = root;
    for (char ch: encoding.toCharArray()) {
        curr = ch == '0' ? curr.left : curr.right;
        if (curr.data != '\0') {
            result.append(curr.data);
            curr = root;
        } 
    }
    System.out.println(result);
}

I have just copy pasted ur code except using sysout statement instead of string buffer

  Node c = root;
    for (int i = 0; i < S.length(); i++) {
        c = S.charAt(i) == 1 ? c.right : c.left;
        if (c.left == null && c.right == null) {
            System.out.print(c.data);
            c = root;
        }
    }

But it is printing BBB for given test case which is wrong!! I am doing an overlook??

The root of the node tells how many characters there are , so you could initialize the StringBuilder with a capacity of root.frequency.

It's questionable whether System.out.print() is faster, because it may print character by character, which is potentially slower, or maybe System.out uses an internal buffer and prints it out once the size goes past a threshold.

I don't get it what's the use of String builder. Modified your code.

Node c = root; char ch; for(int i = 0;i

This will not work if tree has only one node i.e. root. The c will become null after either c.right or c.left operation.

This java solution and the recursive one doesn't work for the input string coding 'AA' for example. You'll output one single A or nothing.

1. Take S.length into an int variable. To avoid recomputing it for every loop.
2. Check c.data != '\u0000' instead of checking its left and right node.
3. Take the string into char[] again to avoid calling charAt and recomputing for every character from the original string.

I agree with your use of StringBuilder instead of just printing the character out.(I just saw the editorial has the same logic)

This doesn't work for the case when the input is only one char. Easy fix: check if the root is a leaf before anything else.

you are not using tree concept;

nice one!

C++ solution :

void decode_huff(node * root, string s) {
    int index=0;
    char ch;
    node* ptr=root;
    while(index!=s.size())
    {
        ch=s[index++];
        ptr=((ch=='1')?ptr->right:ptr->left);
        if (ptr->data)
        {
            cout << ptr->data;
            ptr=root;
        }
    }
}

I did the same but evaluating the data field for the leaves, which are null (0x00) by definition. Good introduction to the Huffman coding theory.

You don't have to input anything. It is a function only submission. The input is handled by the main program. You just need to implement the function as described in the problem.

Thanks, I was looking to optimize my C++ solution. I think you might enjoy using a for-each loop here:

void decode_huff(node * root,string s)
{
    node* temp = root;
    for (char c : s) {
        temp = c == '0' ? temp->left : temp->right;
        if (temp->data) {
            cout << temp->data;
            temp = root;
        }
    }
}

first time to know the grammer that'n=0;s[n];n++'!

I agree with you. Python must be added as a supported language for all problems.

Short and crisp!

can you pls explain me how this line work:

str.charAt(i) == '0'

Here there is no use of use of frequency as per this question . It was only meant to explain the concept of Huffman-Coding . Well Answered !! .