Iterative Inorder Traversal

0
votes

Here is my function for iterative inorder traversal. But when I execute it I'm getting a segmentation fault. I'm using a stack for the traversal. In the given program I also have a recursive function for inorder traversal to check if my create() function is working.

I'm pushing the node to the stack and moving to the left of the node and after that I'm popping the node from the stack and printing it and going to the right by doing root=root->rlink.

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *llink;
struct node *rlink;
}Node;
typedef struct Stack
{
Node *a[10];
int top;
}stack;
void push(stack *s,Node *root)
{
if(s->top==9)
    printf("FULL");
else
{
    s->top++;
    s->a[s->top]=root;
}
}
Node *pop(stack *s)
{
    if(s->top==-1)
        printf("Empty");
    return s->a[s->top--];
}
void inorder(Node *root)
{
    stack s;
    s.top=-1;
    int flag=1;
    while(flag)
    {
    if(s.top!=9)
    {
        push(&s,root);
        root=root->llink;
    }
    else{
        if(s.top!=-1)
        {
            root=pop(&s);
            printf("%d",root->data);
            root=root->rlink;
        }
        else
            flag=0;
    }
    }
}
void inor(Node *root)
{
if(root!=NULL)
{
inor(root->llink);
printf("%d",root->data);
inor(root->rlink);
}
}
Node *create(Node *root,int key)
{
if(root==NULL)
{
root=(Node *)malloc(sizeof(Node));
root->data=key;
root->rlink=root->llink=NULL;
}
else
{
if(key>root->data)
{
    root->rlink=create(root->rlink,key);
}
else if(key<root->data)
{
root->llink=create(root->llink,key);
}
}
return root;
}
int main()
{
    Node *h=NULL;
    h=create(h,5);
    h=create(h,1);
    h=create(h,3);
    h=create(h,8);
    h=create(h,12);
    h=create(h,51);
    inorder(h);
    //inor(h);
}
3
cdata-structuresbinary-treebinary-search-tree
Have you used a debugger to find out immediately which line is causing the seg fault and to trace the execution of your program ? – kaylum
Make sure your terminate diagnostic printing messages with a newline (or use fflush(stdout);) — otherwise, you may never see the message if the code crashes, giving you the wrong impression about where the crash occurs. – Jonathan Leffler
@kaylum yah i did that but I cant figure it out – Sagar Goyal
@JonathanLeffler oaky I'll do that – Sagar Goyal
Ok so at then at least tell us which line triggered the seg fault. The debugger gives you that immediately. – kaylum

3 Answers

1
votes

As diagnosed in my main comment, the problem is that your code didn't stop traversing leftwards when there was no further node in that direction. The fix is simple:

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

typedef struct node
{
    int data;
    struct node *llink;
    struct node *rlink;
} Node;

typedef struct Stack
{
    Node *a[10];
    int top;
} stack;

static
void push(stack *s, Node *root)
{
    if (s->top == 9)
        printf("FULL\n");
    else
    {
        s->top++;
        s->a[s->top] = root;
    }
}

static
Node *pop(stack *s)
{
    if (s->top == -1)
        printf("Empty\n");
    return s->a[s->top--];
}

static
void inorder(Node *root)
{
    stack s;
    s.top = -1;
    int flag = 1;
    while (flag)
    {
        //printf("I: %p\n", (void *)root);
        if (s.top != 9 && root != 0)
        {
            push(&s, root);
            root = root->llink;
        }
        else
        {
            if (s.top != -1)
            {
                root = pop(&s);
                printf(" %d", root->data);
                root = root->rlink;
            }
            else
                flag = 0;
        }
    }
}

static
void inor(Node *root)
{
    if (root != NULL)
    {
        inor(root->llink);
        printf(" %d", root->data);
        inor(root->rlink);
    }
}

static
Node *create(Node *root, int key)
{
    if (root == NULL)
    {
        root = (Node *)malloc(sizeof(Node));
        root->data = key;
        root->rlink = root->llink = NULL;
    }
    else
    {
        if (key > root->data)
        {
            root->rlink = create(root->rlink, key);
        }
        else if (key < root->data)
        {
            root->llink = create(root->llink, key);
        }
    }
    return root;
}

int main(void)
{
    int nodes[] = { 37, 2, 19, 9, 7, 41 };
    enum { NUM_NODES = sizeof(nodes) / sizeof(nodes[0]) };
    Node *h = NULL;
    h = create(h, 5);
    h = create(h, 1);
    h = create(h, 3);
    h = create(h, 8);
    h = create(h, 12);
    h = create(h, 51);
    printf("Recursive:\n");
    inor(h);
    putchar('\n');
    printf("Iterative:\n");
    inorder(h);
    putchar('\n');

    for (int i = 0; i < NUM_NODES; i++)
    {
        h = create(h, nodes[i]);
        printf("Iterative:\n");
        inorder(h);
        putchar('\n');
    }
}

I use static on the functions because my default compiler options require functions to be declared or defined before use, and only static functions can be defined without being pre-declared:

gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition it37.c -o it37

You can decide whether that matters to you for yourself (but I note that no file other than this one needs to access the functions, so 'information hiding' suggests that the functions should be static).

Sample output:

Recursive:
 1 3 5 8 12 51
Iterative:
 1 3 5 8 12 51
Iterative:
 1 3 5 8 12 37 51
Iterative:
 1 2 3 5 8 12 37 51
Iterative:
 1 2 3 5 8 12 19 37 51
Iterative:
 1 2 3 5 8 9 12 19 37 51
Iterative:
 1 2 3 5 7 8 9 12 19 37 51
Iterative:
 1 2 3 5 7 8 9 12 19 37 41 51
0
votes

As given in above comments, "root" in your code always got assigned address of the left node and when leaf node was reached it had "NULL" values in it and you can't access null that is the reason why your code failed and would have gave you segmentation fault.

anyways here is my code resolving your error

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


typedef struct node
{
    int data;
    struct node *llink;
    struct node *rlink;
}Node;


typedef struct Stack
{
    Node *a[10];
    int top;
}stack;

void push(stack *s,Node *root);
Node *pop(stack *s);
void inorder(Node *root);



void push(stack *s,Node *root)
{
    if(s->top==9)
    {
        printf("FULL");
    }
    else
    {
        s->top++;
        s->a[s->top]=root;
    }
}


Node *pop(stack *s)
{
    if(s->top==-1)
    {
        printf("Empty");
        return  NULL;
    }

    return s->a[s->top--];
}
void inorder(Node *root)
{
    stack *s;// took it as a pointer so that i could use it easily
    s=(stack *)malloc(sizeof(stack));
    s->top=-1;//initialized to -1 because we increment top then insert at location indicated by top
    int flag=1;
    bool traverse_left=true;

    while(flag)
    {
        if( root->llink!=NULL && traverse_left )//if left link available go left
        {
            push(s,root);
            root=root->llink;
        }
        else if((root->llink==NULL&&root->rlink!=NULL)||(root->llink!=NULL && !traverse_left))
        {
            printf("%d  ",root->data);
            root=root->rlink;
            traverse_left=true;
        }
        else if(root->llink==NULL&&root->rlink==NULL)
        {
            printf("%d  ",root->data);
            if(root->llink==NULL&&root->rlink==NULL&&s->top==-1)
            {
                flag=0;
            }
            else
            {
                root=pop(s);
            }
            traverse_left=false;
        }


    }
}


void inor(Node *root)
{
    if(root!=NULL)
    {
        inor(root->llink);
        printf("%d",root->data);
        inor(root->rlink);
    }
}

Node *create(Node *root,int key)
{
    if(root==NULL)
    {
        root=(Node *)malloc(sizeof(Node));
        root->data=key;
        root->rlink=root->llink=NULL;
    }

    else
    {
        if(key>root->data)
        {
            root->rlink=create(root->rlink,key);
        }
        else if(key<root->data)
        {
            root->llink=create(root->llink,key);
        }
    }

return root;
}
int main()
{
    Node *h=NULL;

    h=create(h,5);
    h=create(h,1);
    h=create(h,3);
    h=create(h,8);
    h=create(h,12);
    h=create(h,51);

    inorder(h);
    //inor(h);
}

  • In this program whenever we go for a left node i put that node in stack before we moved on to left node

  • while traversing back if stack contains left node it means we have already traversed left tree of it so I pop it and start traversing it's right sub tree

  • if a node's left and right pointers are null i pop of the node from stack and start traversing it's right sub tree

If you have any doubts regarding this answer please comment.

0
votes

Inorder traversal: left, parent, right

Key idea of iterative traversal using a stack is:

  1. Go left (also push into stack) until null found.

  2. Run while loop until stack is empty. Each time pop top element, add it into result list. Then if right child exist, go to right child (also push into stack) and then go left (also push into stack) until null found. So basically code for step 1 will be copied inside of while loop.

Code looks like:

class Node {
    int key;
    Node left, right;

    public Node() {}

    public Node(int key) {
        this.key = key;
    }
}
public List<Integer> inOrderIterative() {
    List<Integer> list = new ArrayList<>();
    Stack<Node> nodeStack = new Stack<>();
    Node current = root;
    nodeStack.push(current);
    while (null != current.left) {
        current = current.left;
        nodeStack.push(current);
    }

    while(!nodeStack.empty()) {
        current = nodeStack.pop();
        list.add(current.key);

        if (null != current.right) {
            current = current.right;
            nodeStack.push(current);
            while (null != current.left) {
                current = current.left;
                nodeStack.push(current);
            }
        }
    }

    return list;
}