Two questions on Binary Search Trees

I have two questions about binary search trees - one about the code I am writing and the other more about theory. First of all, the code that I wrote below works fine except for when I try to display the case where the BST is actually empty; it gives me a segmentation fault when I would like it to print out an error message. I feel like I may have gotten my pointers mixed up at some point and so that is giving me the error. Here is my code:

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

struct Node {
char *word;
struct Node *left;
struct Node *right;
};

/* Function that creates a new node as a leaf; that is, its     */
/* left and right children are NULL.                */
/* Require: node -> word != NULL                    */
struct Node * createNode (char *word) {
struct Node *item = malloc(sizeof(struct Node));
item -> word = word;
item -> left = NULL;
item -> right = NULL;
return item;
}

/* Recursive function that inserts a node into proper position by   */
/* searching through    tree.                   */
struct Node * insertNode (struct Node *root, char *word) {
// If tree is empty, node becomes root
if(root == NULL)
    return createNode(word);
else {

    if(strcmp(word, root -> word) < 0) {
        root -> left = insertNode(root -> left, word);
        return root;
    } else if(strcmp(word, root -> word) > 0) {
        root -> right = insertNode(root -> right, word);
        return root;
    } else if(strcmp(word, root -> word) == 0)
        printf("Word is already present in the tree.");
}
}

/* Function to display Binary Search Tree via inorder traversal.    */
/*  -- prints entire left subtree, then root, then right subtree    */
void display (struct Node *root) {
if(root -> word == NULL)
    printf("Tree is empty.");
if(root -> left != NULL)
    display(root -> left);
printf("%s\n", root -> word);
if(root -> right != NULL)
    display(root -> right);
}

void main () {
struct Node root;
struct Node *rootP = &root;
root = createNode("
}

The second question involves populating the binary tree. I want to use a 开发者_运维问答small dictionary which will of course be in alphabetical order. If I feed those words into the binary tree starting with, say, "aardvark," won't the tree end up incredibly skewed as all subsequent words will come after the first alphabetically and thus always be right children? I'm afraid that I will end up with a tree that is incredibly off balance! Is there some method I can use to shuffle the tree around as I am populating it?

Thank you for taking the time to read this!

---

In your display function, you first need to test whether root == null before testing whether root -> word == null. That should fix the seg fault.

Regarding the theory question: the answer is that yes, the tree will end up incredibly skewed. That's what balanced binary trees are all about.

---

if(root -> word == NULL)
    printf("Tree is empty.");

Your problem lies here. What happens if root itself is null? Double check that pointer before de-referencing it.

Yes, if you insert items in sorted order (or relatively sorted), you'll get a skewed tree. Look into algorithms on rotations for nodes in balanced binary trees.

---

Regarding your second question, others have already mentioned looking into balancing your binary tree. However, as an alternative, if your input is already known to be sorted, then it is more appropriate instead to use a linear array with a binary search to find items of interest, rather than a binary tree. A binary search of a sorted array has the same time complexity as a search in a balanced binary tree.