Sunday, October 20, 2013

[Amazon interview] Leftmost node at each level in a tree

Print the leftmost node of each level in a tree.
Posted by at

1 comment:

  1. Priyanka SinghOctober 20, 2013 at 8:38 AM

    Idea is simple. We just have to do level order traversal of a tree and print the leftmost node in a tree.

    #include
    #include
    #define MAX_QSIZE 50
    typedef struct node
    {
    int data;
    struct node *left, *right;
    }node;

    node *newNode(int data)
    {
    node *newNode=(node*)malloc(sizeof(node));
    newNode->data=data;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode;
    }
    node **createQueue(int *front, int *rear)
    {
    node **queue=(node**)malloc(sizeof(node*)*MAX_QSIZE);
    *front=*rear=0;
    return queue;
    }
    void enqueue(node ** queue, int *rear, node *new_node)
    {
    queue[*rear]=new_node;
    (*rear)++;
    }
    node *dequeue(node ** queue, int *front)
    {
    (*front)++;
    return queue[*front-1];
    }
    void printLeftMost(node* root)
    {
    int front, rear;
    node **queue=createQueue(&front, &rear);
    node *temp_node=root;
    printf("%d ", temp_node->data);
    while(temp_node)
    {
    if(temp_node->left)
    {
    printf("%d ", temp_node->left->data);
    enqueue(queue, &rear,temp_node->left);
    }
    if(temp_node->right)
    enqueue(queue, &rear,temp_node->right);
    temp_node=dequeue(queue, &front);
    }
    }

    int main()
    {
    node * root=newNode(1);
    root->left=newNode(2);
    root->right=newNode(4);
    root->left->left=newNode(3);
    root->right->left=newNode(5);
    printLeftMost(root);
    getch();
    return 0;
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)