Find the largest lexicographically root to leaf path in binary tree

Question

I have to create binary tree in which nodes store a char value. The task is to find the largest lexicographically root to leaf path created by these chars.

The given input should be a string where first char is value to store and after space there are hints in which node it is stored. L means left node, R of course right one. The output should be a found string and number of chars given in input (not whitespaces).

This is my code. I'm pretty sure that mistake is in rootToLeafPath(), because I've already checked method which creates tree. I'm giving you also, print method if you want to see all paths.

#include <stdio.h>
#include <iostream>
#include <string.h>
int allCharCounter = 0;
char oldest_word[65];

struct Tree_node{
    struct Tree_node *right;
    struct Tree_node *left;
    char value;
};

Tree_node* getTree(struct Tree_node* root){
    char c = getchar();
    char edge = c;
    Tree_node* korzen = new Tree_node();
    if(root == NULL){
        root = new Tree_node(); 
    }
    korzen = root;
    while(!feof(stdin)){
        c = getchar();
        if(c == 82){//R
            allCharCounter++;
            if(root->right == NULL){
                root->right = new Tree_node();
            }
            root = root->right;
        }else if(c == 76){//L
            allCharCounter++;
            if(root->left == NULL){
                root->left = new Tree_node();
            }
            root = root->left;
        }else if(c > 96 && c < 123){
            allCharCounter++;
            root->value = edge;
            root = korzen;      
            edge = c;
        } 
    }
    root->value = edge;
    root = korzen; 
    return root;
}

void printPath(char *path, int length){
    int i;
    for(i = 0; i <= length; i++){
        printf("%c ", path[i]);
    }
    printf("\n");
}

void rootToLeafPath(struct Tree_node *nodeptr, char *current_path, int index){

    if(nodeptr != NULL){
        current_path[index] = nodeptr->value;
        if(nodeptr->left == NULL && nodeptr->right == NULL){
            if(strcmp(oldest_word,current_path)< 0){
                //memset(oldest_word,0,sizeof(oldest_word));
                strncpy(oldest_word, current_path, 65);
            }
            //printPath(current_path, index);
        }
        rootToLeafPath(nodeptr->left, current_path,index+1);
        rootToLeafPath(nodeptr->right, current_path,index+1);
    }
}



int main(){
    struct Tree_node* root = NULL;
    struct Tree_node* test = NULL;
    root = getTree(root);
    char current_path [65] ={};
    rootToLeafPath(root, current_path,0);
    std::cout<< oldest_word;
    fprintf(stdout,"\n%d", allCharCounter+1); //-> ok
}

So for input:

s LR

z LRR

m RR

p LRLRL

k

w LRL

a LL

t L

h R

j LRLR

a LRRR

The output should be:

ktsza

38

But my code creates:

ktszap

38

I thought maybe I need to clear oldest_word before giving it a new value, but didn't work. For me it looks like it remembers longer value which was before. In this example, 'ktswjp' was the word in array before, but then it found new one which was 'ktsza', but the 'p' stayed.

Appreciate any help.

1201ProgramAlarm 1201ProgramAlarm · Accepted Answer · 2017-12-16T19:03:50

In rootToLeafPath, you assign a value to current_path[index] = nodeptr->value; to store the next character. When you're done with that character, you don't clear it out so it stays in the buffer, resulting in it appearing at the end of strings that should be shorter.

The solution is to reset it to the nul character before you return, with

current_path[index] = '\0';

after your recursive calls to rootToLeafPath are done.

Find the largest lexicographically root to leaf path in binary tree

1 Answers