Tuesday, 30 June 2015

Print all paths from root to leaf node in a binary tree


Maintain an array path[] having node's data on each level , and the length of path[] , on every  new level oush the node's data to path[] and increment path len.
If we are at the leaf node ,  print the path[] , or try recursing to left and right child 

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen);

void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}
void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void printPaths(struct node* node)
{
    int path[1000];
    printPathsRecur(node, path, 0);
}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen)
{
    if (node == NULL)
    {
        return;
    }
   
    //add the node to path at this level
    pat[pathlen] = node -> data;
    //increment path len
    ++pathlen;

    //if its a leaf node , print the path
    if (node->right == NULL && node->left == NULL)
    {
        printArray(pat, pathlen);
    }
    else
    {
        //try bith subtree
        printPathsRecur(node->left, pat, pathlen);
        printPathsRecur(node->right, pat, pathlen);
    }
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print all root-to-leaf paths of the input tree */
    printPaths(root);

    getchar();
    return 0;
   
}

No comments:

Post a Comment