Level Order Traversal

void levelorder( TreeNode <int> * treeNode ) {
    Queue <TreeNode<int> *> q;

    if(treeNode == NULL) return;

    q.enqueue(treeNode);

    while(!q.empty()) {
        treeNode = q.dequeue();
        cout << *(treeNode->getInfo()) << " ";

        if(treeNode->getLeft() != NULL)
            q.enqueue(treeNode->getLeft());

        if(treeNode->getRight() != NULL)
            q.enqueue(treeNode->getRight());
    }

    cout << endl;
}

Binary Search Tree with Strings

void wordTree() {
    TreeNode<char> * root = new TreeNode<char>();

    static char * word[] = {"babble", "fable", "jacket",
    "backup", "eagle","daily","gain","bandit","abandon",
    "abash","accuse","economy","adhere","advise","cease",
    "debunk","feeder","genius","fetch","chain", NULL};

    root->setInfo(word[0]);

    for(i = 1; word[i]; i++)
        insert(root, word[i]);

    inorder(root);
    cout << endl;
}

void insert(TreeNode<char> * root, char * info) {
    TreeNode<char> * node = new TreeNode<char>(info);
    TreeNode<char> *p, *q;
    p = q = root;

    while(strcmp(info, p->getInfo()) != 0 && q != NULL ) {
        p = q;

        if( strcmp(info, p->getInfo()) < 0 )
            q = p->getLeft();

        else
            q = p->getRight();
    }

    if(strcmp(info, p->getInfo()) == 0) {
        cout << "attempt to insert duplicate: " << * info << endl;
        delete node;
    }

    else if(strcmp(info, p->getInfo()) < 0)
        p->setLeft(node);

    else
        p->setRight(node);
}

Deleting a Node from BST

There are 2 cases while deleting nodes from the binary-search-tree: 1. The node is a leaf node. 1. 2. The node is not a leaf node and has only one subtree. 1. 3. The node is not a leaf node and has both subtrees. 1.

For 2nd case, the parent node of the node to be deleted, has to be re-adjusted to point to the inorder successor of the node to be deleted.

For 3rd case, assume we want to delete the node with value 2.
Firstly, we find the left most node of the right subtree.
Copy its contents into the node to be deleted.
Then do the procedure used in 2nd case.