0

Below is the program which converts a sorted Array to BST. I am able to compile and execute the program using an online C compiler. When I tried the compile on my local system, it is throwing a segmentation fault.

SortedArraytoBST.c

#include <stdio.h>
#include <stdlib.h>

// Structure of the node
struct TNode
{   
    int data;
    struct TNode* left;
    struct TNode* right;
};

struct TNode* newNode(int data);

// Function that converts array to BST
struct TNode* SortedArrayToBST(int arr[], int start, int end)
{
    if(start > end)
    {
        return NULL;
    }
    if(start == end)
    {
        struct TNode* newnode2 = newNode(arr[start]);
        return newnode2;
    }
    int mid = (start+end)/2;
    struct TNode* newnode = newNode(arr[mid]);
    newnode->left = SortedArrayToBST(arr, start, mid-1);
    newnode->right = SortedArrayToBST(arr, mid+1, end);
    return newnode;
}

//NewNode Creation
struct TNode* newNode(int data)
{
    struct TNode* node = (struct TNode*)malloc(sizeof(struct TNode*));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Print the tree in preorder
void preorder(struct TNode* node)
{
    if( node == NULL) return;
    printf("%d\n", node->data);
    preorder(node->left);
    preorder(node->right);
}

// Array to BST
int main()
{
    int arr[]={1,2,3};
    int size = sizeof(arr)/sizeof(arr[0]);
    struct TNode* root = SortedArrayToBST(arr, 0, size-1);
    preorder(root);
    return 0;
}

Command used to compile the program

$ gcc -o SortedArraytoBST SortedArraytoBST.c
$ gcc --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 7.0.2 (clang-700.1.81)
Target: x86_64-apple-darwin15.2.0
Thread model: posix
$

Output of the program on my local Mac

    2
    -398445936
    Segmentation fault: 11

Output of the program on http://code.geeksforgeeks.org/

    2
    1
    3
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Venky
  • 11
  • 2
  • You're using clang locally, not gcc 4.2.1. Anwyay, if you have a segmentation fault, you can get a core file to examine. What happened when you opened it in the debugger? What happened when you stepped through your program in the debugger? – Useless Jan 14 '16 at 17:30
  • @useless Thank you for looking into it. How to make GCC point to gcc 4.2.1 instead of clang. I don't know where the core file gets created after the segmentation fault. So, I haven't ran any debugger. I will try to get the corefile location and debugger output. Meanwhile why it is throwing a segmentation fault in my local system and the same code works fine if i run it using a online compiler – Venky Jan 15 '16 at 20:40
  • What makes you think it's the compiler's fault? The "it runs fine here" problem is as old as programmers. – Randy Howard Jan 16 '16 at 20:00

1 Answers1

1

Line 36, you have a wrong allocation causing a heap-buffer-overflow.

You should write:

struct TNode* node = (struct TNode*)malloc(sizeof(struct TNode));

instead of: 

struct TNode* node = (struct TNode*)malloc(sizeof(struct TNode*));

HOW TO DEBUG IT

If you get gcc 4.8 or above, you can run address sanitizer:

gcc -fsanitize=address -fno-omit-frame-pointer -g myprogram.c -o myprogram

What I got:

=================================================================
==22711==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000eff8 at pc 0x000000400bbb bp 0x7ffea7e3c630 sp 0x7ffea7e3c628
WRITE of size 8 at 0x60200000eff8 thread T0
    #0 0x400bba in newNode /home/jyvet/TMP/myprogram.c:38
    #1 0x400aac in SortedArrayToBST /home/jyvet/TMP/myprogram.c:27
    #2 0x400d75 in main /home/jyvet/TMP/myprogram.c:57
    #3 0x7f68db2c7b44 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b44)
    #4 0x4008e8  (/home/jyvet/TMP/myprogram+0x4008e8)

0x60200000eff8 is located 0 bytes to the right of 8-byte region [0x60200000eff0,0x60200000eff8)
allocated by thread T0 here:
    #0 0x7f68db6e337a in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x9437a)
    #1 0x400b59 in newNode /home/jyvet/TMP/myprogram.c:36
    #2 0x400aac in SortedArrayToBST /home/jyvet/TMP/myprogram.c:27
    #3 0x400d75 in main /home/jyvet/TMP/myprogram.c:57
    #4 0x7f68db2c7b44 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b44)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/jyvet/TMP/myprogram.c:38 newNode
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
jyvet
  • 2,021
  • 15
  • 22
  • Even better, use `struct TNode* node = (struct TNode*)malloc(sizeof(*node));` (and there are a lot of zealots who would [insist on removing the cast](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) too: `struct TNode* node = malloc(sizeof(*node));`. Another valuable debugging tool is [`valgrind`](http://valgrind.org/). – Jonathan Leffler Jan 17 '16 at 00:46
  • @Jonathan Thank you very much. I am new to these things, Are there any resources to learn more about debugging or how to use valgrind. Every time i am facing compilation issue, i am trying to find the cause using google or stack overflow. – Venky Jan 17 '16 at 19:55
  • @Venkat: Tools like `valgrind` and even debuggers won't help with compilation issues. They come into play once the program is linked and running. It isn't always obvious what's best to do with compilation problems per se. Usually, the first error message is strongly indicative of what's wrong; subsequent errors might just be a consequence of the first, or might be independent problems. Experience will help you determine which is which. – Jonathan Leffler Jan 17 '16 at 20:01
  • @Venkat: For runtime problems, the first key is to ensure that the code compiles cleanly under the most stringent warnings you can manage. Then it becomes a game of "what's going wrong" to decide the correct tool(s) to use. If it is crashing, simply running the code under a debugger tells you where the problem occurs. That can often help. Semi-stable code benefits from `valgrind` — or when you're moderately sure that dynamic memory management is the core of the problem. I've not used ASAN much — through ignorance rather than because I have any reason not to use it. – Jonathan Leffler Jan 17 '16 at 21:04