how to find last level of red black tree?

Question

I have a simple implementation of red black tree.I want to print nodes of last level this tree.I know that my tree has 15 node.So i want 3th level of the tree.If i put index for nodes and find them how to do this work?Or exist another way ?

typedef enum {RED, BLACK} nodecolor ;
struct node{
    node * left;
    node * right;
    node * parent;
    node * nil;
    node * root;
    int * key;
    nodecolor color;
};
node *root=NULL;
void LeftRotate(node* &tree, node* x){
    node* y;
    node* nil=tree->nil;
    y=x->right;
    x->right=y->left;
    if (y->left != nil)
    y->left->parent=x;
    y->parent=x->parent;
    if(x==x->parent->left)
        x->parent->left=y;
    else
        x->parent->right=y;
    y->left=x;
    x->parent=y;
}

void RightRotate(node* &tree, node* y){
    node* x;
    node* nil=tree->nil;
    x=y->left;
    y->left=x->right;
    if (nil != x->right)
    x->right->parent=y;
    x->parent=y->parent;
    if( y == y->parent->left)
    y->parent->left=x;
    else
    y->parent->right=x;
    x->right=y;
    y->parent=x;
}

void InsertFixUp(node * &tree, node *z){
    node *nil=tree->nil;
    node *y;
    while (z->parent->color==RED){
        if(z->parent==z->parent->parent->left){
            y=z->parent->parent->right;
            if(y->color==RED){
                z->parent->color=BLACK;
                y->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            }
            else if(z=z->parent->right){
                z=z->parent;
                LeftRotate(tree,z);
            }
            z->parent->color=BLACK;
            z->parent->parent->color=RED;
            RightRotate(tree,z->parent->parent);
            }
        else{
            y=z->parent->parent->left;
            if(y->color==RED){
                z->parent->color=BLACK;
                y->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            }
            else if(z=z->parent->left){
                z=z->parent;
                LeftRotate(tree,z);
            }
            z->parent->color=BLACK;
            z->parent->parent->color=RED;
            RightRotate(tree,z->parent->parent);
        }
    }
}

void Insert(node *&tree,node*&z){
    node* nil=tree->nil;
    node* root=tree->root;
    node *y;
    node *x;
    y=tree->nil;
    x=tree->root;
    while(x!=tree->nil){
        y=x;
        if((z->key)<(x->key))
            x=x->left;
        else
            x=x->right;
    }
    y=z->parent;
    if(y=tree->nil)
        z=tree->root;
    else if((z->key)<(y->key))
        z=y->left;
    else
        z=y->right;
    z->left=tree->nil;
    z->right=tree->nil;
    z->color=RED;
    InsertFixUp(tree,z);
}

Answer 1

If I correctly understood the question, something like this can work for You:

void printNode( node *n ){
   if( n->left == NULL && node->right == NULL ){
      printf( "node info: %d\n" n->key);
      return;
   }
   if( n->left != NULL )
      printNode( n->left );
   if( n->right != NULL );
      printNode( n->right );
}

Please note: it is not tested code. The idea is to traverse the whole tree using recursive function printing info about nodes which don't have descendants (last level)

I used NULL, where in Your code probably is used nil (You may need to adjust this to Your needs).