10.Traversing A Binary Tree

• All queries, discussions, updates and clarifications related to Session 05.Traversing A Binary Treeshould be posted here.
• DOUBLE POINTER     HERE I'M EXPRESSING A DEEP ROOTED CONCEPT

**tree   is a double pointer or array of pointers

pointer notation    array notation
*(tree+0)   is same as  tree[0]       // THIS IS ACTUALLY AN ADDRESS NOT A DATA VALUE

if *(tree+0) = NULL
tree[1] = NULL

then
printf( "\n *( tree+0 ): %p", *( tree+0 ) );
printf( "\n tree[1]: %p", tree[1] );

result:
NULL
NULL
-----------------------------------        --------------------------------   -----------------------------
typedef struct node
{
Node* left;
int data;
Node* right;
}Node;
tree[1]->data             will give the value at 1st location in double pointer.

as also depicted in :

typedef struct Item
{
struct Item *next;
void **data;
}Item;

Item* curr->data = (void**)malloc(  sizeof(char*)*no_of_reg);
copy_from_user( curr->data[i], ubuff, 1 );          // to kernelspacedataAddress, from UserSpaceDataAddress, sizeofdata
• Node **tree;

tree = (Node**)realloc(tree, sizeof(Node*)*2);

tree[0] = NULL;
tree[1] = (Node*)creatNode(0);

printf( "children: %p",  *(tree+0) );
printf( "children: %p",  tree[0] );

printf( "children: %p",  *(tree+1) );
printf( "children: %p",   tree[1] );

Result:

creatNode: End
children: (nil)children: (nil)children: 0x1ecbae0children: 0x1ecbae0creatTree: End
• Yes, you are correct. The expressions *(tree + 0) and tree[0] are equivalent in C.

*(tree + 0) is using pointer arithmetic to calculate the address of the element at index 0 in the array pointed to by tree and then dereferencing that address to get the value.
tree[0] is using the array subscript notation to directly access the value at index 0 in the array pointed to by tree.
• RAW observ:

typedef struct node
{
Node* parent;
int data;
Node** children;
}Node;

tree[1] = NULL;

tree[1] = (Node*)realloc(tree, sizeof(Node*));   // Node size allocation

tree[1]->children = (Node**)realloc( tree[1]->children,  sizeof(Node*)*2 );

then using pointer arithmetic tree[1]->children [0]  or   tree[1]->children[1]   points to NULL after reallocation also.

error :  printf( "%s:  tree[ %d ]->children[0]:address  %p  \n", __func__,  2*j+k+i-1 , temp->children[0] );              // used 3 loops i,j,k to reach to a particular node

tree[1]->chlidren[0]->data is not ACCESSIBLE even after entering value for data.

THIS IS BECAUSE THESE TWO  HAVE BEEN ALLOCATED MEMORY IN FRAGMENTED WAY.
we have used a double linked list here for memory representation.

THIS IS POSSIBLE ON USE OF 1-D ARRAY INSTEAD OF double LinkedList use.

• So, a better way is to use a 1-D array for a tree  & a double linked list for a BINARY Search Tree.

THE SIMPLICITY LIES IN using left and right nodes for a binary search tree for traversal.

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

This is an easy way .
• DELETION IN BST:  corrected code

Node* deleteElement( Node* tree, int val)
{
printf("%s:Begin \n", __func__)

Node* cur, *parent, *suc, *psuc, *ptr;
parent = tree;
cur = tree->left;

while( cur!= NULL && val!= cur->data)
{
parent = cur;
cur = (val < cur->data)? cur->left : cur->right;
}

if( cur->left == NULL )       // single child node deletion
ptr = cur->right;
else if( cur->right == NULL )
ptr = cur->left;
else                          // both child node deletion
{
// find the in-order successor and its parent
psuc = cur;
suc = cur->right;

while( suc->left != NULL)
{
psuc = suc;
suc = suc->left;
}

if( psuc == cur)
{
psuc->right = suc->right;
}
else
{
suc->left = cur->left;
psuc->left = suc->right;
suc->right = cur->right;

}

ptr = suc;

}

// attach ptr to the parent node
if( parent->left == cur)
parent->left = ptr;
else
parent->right = ptr;

free( cur);

return tree;

printf("%s:End \n", __func__);

}