recursion - C: Finding Huffman-coded path of specific leaf in tree -

i'm trying write recursive function locates specific leaf within huffman tree, prints shortest path zeros , ones (zero being traversal left, , 1 being traversal right). understand logic of need do, i'm not having success @ implementing it. believe have skeleton here, part i'm missing more complicated logic tell when should run printf , when should not (since prints every 0 , one). also, know rest of logic outside of working because if normal traversal not have plot shortest paths, each of elements searching found.

i've tried looking @ quite few resources online , cannot find solution, or @ least, cannot recognize solution properly. i've rewritten 50 or more times. let me know think!

void traverse(struct tree *curr, struct tree *cmp) {   if (curr == null)   {     return;   }    if (getleft(curr) == null && getright(curr) == null)   {     if (curr == cmp)     {       return;     }   }    if (getleft(curr) != null)   {     printf("0");      traverse(getleft(curr), cmp);   }    if (getright(curr) != null)   {     printf("1");      traverse(getright(curr), cmp);   } } 

for context: cmp node want find, getleft() , getright() return left , right children of node respectively, , curr starts root of huffman tree itself. also, reason printf thing works because loop through of known leaves, print other information leaf, , call traversal method, followed newline.

there several solutions.

first, traverse entire tree doing , build table of codes. use table, not tree. you're not wasting time searching whole tree every code. traverse tree build string of 0's , 1's, , when leaf, save built string , symbol in leaf in table. throw away tree. recommended approach.

second, links bidirectional. since have pointer leaf, start @ leaf , work way root, constructing string of 0's , 1's in reverse.

third, persist in doing painful tree search every leaf having traverse function return true or false. return true if either got desired leaf, or if 1 of traverse calls returned true. depending on traverse call returned true, print or save 0 or one. print path in reverse. if save them in string in reverse order instead of printing, can print string when first traverse call returns.