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 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!

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 !! .

For this type of tree, you don't have to check if both left and right leaves exist - each node has either 2 or 0 leaves.

That should let you shorten your second while statement to "while current.left:"

I had a similar solution, but refactored out one while loop (and changed the other to for-in) based on comments here.

def decodeHuff(root, s):
    curr = root
    result = ''
    
    for i in s:
        if i == '0':
            curr = curr.left
        else:
            curr = curr.right
            
        if not curr.left and not curr.right:
            result += curr.data
            curr = root
    
    print(result)

Python support is now added .