Creating a Binary Search Tree node with Parent node

Question

I have a BST defined as follows:

typedef struct trnode {
    Item item;
    struct trnode *left;
    struct trnode *right;
} Trnode;

typedef struct tree {
    Trnode *root;
    size_t size;
} Tree;

The issue I'm having is often I want to know what the parent of a particular tree node is. Is it common at all to define a tree node which includes the parent, such as:

typedef struct trnode {
    Item item;
    struct trnode *parent;
    struct trnode *left;
    struct trnode *right;
} Trnode;

Or is including the parent something that should not be done, and if so: why not?

---

Update: someone has requested to see my deletion code. This is untested and was pretty difficult for me to write (I'm a beginniner in C and also just learning the BST data structure). Anyways, here it is:

Node * SeekInsertionParent(const Node *root, const Node *pnode)
{
    // cmp returns -1 (less than), +1 (greater than), or 0 (equal)
    int cmp = CmpNodes(pnode, root);
    if (cmp == 0) return NULL; // ignore this for now
    Node *child = (cmp < 0)? root->left : root->right;
    if (child == NULL)
        return root;
    else
        SeekInsertionParent(child, pnode);
}
Bool DeleteItem(Tree *ptree, const Item *pi)
{
    Node *parent;
    Node *node = SeekItem(pi, ptree);
    if (node == NULL)
        return false;

    // (1) if no children, then it's a leaf, just delete it
    if (!node->left && !node->right) {
        free(node);
        return true;
    }

    // (2) if it has one child, link that child to the parent then free the node
    if (!node->left || !node->right) {
        Node *descendant = (node->left)? node->left : node->right;
        descendant->parent = parent;
        if (parent->left == node)
            parent->left = descendant;
        else
            parent->right = descendant;
        free(node);
    }

    // (3) if it has two children, then:
    //     (a) attach the child same-side child to the parent node;
    //     (b) using the root of the attachment, find the place to insert the other-side child
    else {
        Node *insert_at, *other_side;
        if (parent->left == node) {
            node->left->parent = parent;
            parent->left = node->left;
            other_side = node->right;
        } else {
            node->right->parent = parent;
            parent->right = node->right;
            other_side = node->left;
        }

        free(node);
        insert_at = SeekInsertionParent(parent, other_node);

        if (insert_at->left == NULL) {
            insert_at->left=node;
            node->parent=insert_at;
        } else {
            insert_at->right=node;
            node->parent=insert_at;
        }
    }
    return true;
}

Answer 1

As promised, the simplified version, using a pointer-to-pointer.

The point is: you do not need to maintain the parent pointer, since it can always be computed. I created two helper functions to obtain a pointer to the pointer that points to a given node (or value). The same helper functions can be used in an insert-function.

---

#if 0
#include <stdlib.h>
#include <stdbool.h>
#define Bool bool
#else
typedef enum bool{ false, true} Bool;
void free(void*);
#define NULL (void*) 0
#endif

typedef struct node {
    int item;
    struct node *left;
    struct node *right;
} Node;


        // Helper function to find the pointer that points to the node containing item
static Node **node_seek_parent_pp_value(Node **pp, int item)
{
    // cmp returns -1 (less than), +1 (greater than), or 0 (equal)
    while (*pp) {
        int cmp;
        cmp = (*pp)->item == item ? 0 : (*pp)->item < item ? 1 : -1;
        if (cmp == 0) break; // Found!
        pp = (cmp < 0)? &(*pp)->left : &(*pp)->right;
        }

   return pp;
}

        // Same helper function, but with a pointer to item argument
static Node **node_seek_parent_pp_ptr(Node **pp, Node *pnode)
{
if (!pnode) return NULL;
return node_seek_parent_pp_value(pp, pnode->item);
}

Bool DeleteItem(Node **pp, int item)
{
    Node *del;

    pp = node_seek_parent_pp_value(pp, item);
    if (!pp || !*pp) return false; // Not found

    // (1) if fewer than two children
    if (!(*pp)->left || !(*pp)->right) {
        del = *pp;
        *pp = del->left ? del->left : del->right;
    }

    // (2) if it has two children, then:
    //     (a) detach one child subtree
    //     (b) insert it onto the other child
    //     (c) put this other child in place of the node to be deleted.
    else {
        Node **target, *orphan;
        del = *pp;
        orphan = del->right;
        target = node_seek_parent_pp_ptr(&del->left, orphan);
        if (!target) { // should not happen ...
            return false;
            }
        *target = orphan;
        *pp = del->left;
        }

    free(del);
    return true;
}

Bool InsertNode(Node **pp, Node * this)
{
pp = node_seek_parent_pp_ptr(pp, this);
if (!pp || *pp) return false; // this is NULL, or already existing
*pp = this; // insert
return true; // Success!
}

Answer 2

You may want to read this to understand how deletion is done without using parent pointer in node representation. In CLRS, it' given

We can represent such a binary search tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL. The root node is the only node in the tree whose parent is NIL

They use parent pointer since it facilitates to implement procedures like delete, find-next-larger, find-next-smaller, etc. It's not a problem to use it in your code but, it costs O(n) extra memory space. Keep in mind if you don't use parent pointer in the node representation, then you need to implement separate function that takes as argument tree_node and returns parent of tree_node, when you need procedures that requires parent of some nodes.

Answer 3

By adding the parent you will add O(n) memory which is not what you want to do as most of the time your algo will run in O(logN).

If you really want to implement it, you can simply find the model of double LinkedList and replicate this to build BST with parent.

Note that you could take inspiration from XOR Linkedlist to potentially solve the memory surplus:

Trnode(current) = Trnode(parent)^Trnode(current->left ^ current->left)
Trnode(current->left) = Trnode(current)^Trnode(current->left->left^current->left->right)

It is really worth it, especially if you do not need to alter the tree:

• to delete a Trnode from the tree knowing only its address or
• to insert a new node before or after an existing node when knowing only the address of the existing node.