Building a Huffman tree from a binary search tree

Question

I am trying to build a huffman tree out of binary search tree. Sadly my code is crashing (Segmentation fault (core dumped)).

This is how the struct is defined:

struct Node
{
  unsigned char m_ch;
  int m_freq;
  struct Node *m_ls,*m_rs;
  struct Node *m_hls,*m_hrs;
};

delMin is passed a double pointer to a binary search tree, and deletes from it the leftmost leaf unless it reaches a Node with m_ch==0 and return the deleted Node

I can't find my mistake

struct Node *delMin(struct Node **root)
{
    struct Node *current = *root;
    struct Node *b4Current;

    if (current == NULL)
        return NULL;

    while (current->m_ls != NULL)
    {
        if (current->m_ch == 0)
            break;

        b4Current = current;
        current = current->m_ls;
    }

    if (current->m_ch == 0)
        b4Current->m_ls = NULL;
    else
    {
        if (b4Current == NULL)
            *root = current->m_rs;
        else
            b4Current->m_ls = current->m_rs;
    }

    return current;
}


struct Node *huffman(struct Node *root)
{
    struct Node *left;
    struct Node *right;
    struct Node *tempRoot;
    struct Node *huffmanTree;

    while (root->m_ch != 0)
    {
        left = delMin(&root);
        right = delMin(&root);
        tempRoot = createNode((left->m_freq) + (right->m_freq), 0);
        tempRoot->m_hls = left;
        tempRoot->m_hrs = right;
        insertTree(&root, tempRoot);
    }

    huffmanTree = tempRoot;
    return huffmanTree;
}

EDIT: Added code for the insertTree function called by Huffman

void insertTree(struct Node **root,struct Node *n)
{
  if (!*root)
  {
    *root=n;
    return;
  }
  if(n->m_freq<(*root)->m_freq)
  {
    insertTree(&((*root)->m_ls),n);
  }
  else
  {
    insertTree(&((*root)->m_rs),n);
  }
}

Use a debugger or insert puts() calls to determine the exact location where the fault occurs. Then track the associated logic and figure out where the problem is. — cadaniluk
A likely candidate for a segmentaion violation is while (root->m_ch) ...: After removing the last node from the tree, root is NULL and you can't dereference it with ->. So just while (root) should be okay. — M Oehm
If root is a node such that current->m_ls != NULL and current->m_ch==0 the while loop of delMin() is immediately exited. Since current->m_ch==0, the test is entered and b4Current->m_ls=NULL; is executed. But b4Current is not initialized : a segmentation fault can be triggered. — francis
Okay, I see you are making things overly complicated by inserting a dummy node with m_ch == 0. But you don't show how you build the binary tree. — M Oehm

kdopen kdopen · Accepted Answer · 2015-05-14T13:48:04

In delMin this code section

if (current->m_ch == 0)
    b4Current->m_ls = NULL;
else
{
    if (b4Current == NULL)
        *root = current->m_rs;
    else
        b4Current->m_ls = current->m_rs;
}

there is no guarantee that b4Current is not NULL.

Consider the case where the root node has m_ch == 0 and m_ls == NULL. You will take the if branch and dereference b4Current.

You need to initialize b4Current with NULL and check for it before any dereference.

You also need to ensure root itself is non-null before initializing current = *root in delMin or dereferencing it in huffman

These should all be initialized to NULL

struct Node *left;
struct Node *right;
struct Node *tempRoot;
struct Node *huffmanTree;

and it is possible, again, to never enter the while loop, leaving tempRoot unset causing a potential segFault in the caller of huffman when you return its value.

Building a Huffman tree from a binary search tree

1 Answers