Getting all paths from root to leaf nodes

Question

          a
        /    \ 
       a       a
      / \     /  \
     a   c    a   f 
    / \      / \ 
   b   d    e   g

I have a tree that looks like the above, represented by a linked structure:

   class Node
    {
       Node* leftChild; 
       Node* rightChild; 
       char data;
    }

class Tree
{
   Node* root;
}

My goal is to find all the paths from the root to leaf nodes.

My tree traversal algorithm looks like this:

 void inorder()
  {
    in(root);
  }

  void in(CharNode* currentNode)
  {
    if(currentNode)
      {   
        in(currentNode->leftChild);
        cout << currentNode->data << endl;
        in(currentNode->rightChild);
      }   
  }

When I run this, I am positive that the tree is being built as shown. I have tested that. I cannot, however, figure out why my tree traversal segmentation faults.

The output I get is :

b

Segmentation fault.

I have tested it on trees with smaller heights, and it works. But for some reason it doesn't work on a trees with heights larger than 2. I thought it was something going wrong with the tree, I have gone through and printed each parent, left child, and right child and they print out as shown. So it's definitely the traversal algorithm.

Answer 1

/* 
** Binary Tree Problems 
** Printing all Root to Leaf paths in a Binary Tree
*/

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

# define SIZE 20
# define MAX(A,B) A>B?A:B;

typedef struct BinaryTree
{
    int data;
    struct BinaryTree *left;
    struct BinaryTree *right;
}BST;

int A[SIZE]={10,12,15,17,8,18,9,3,11,14,2,1,16,10};
int no_of_nodes=14;



BST* newNode(int data)
{
    BST *node;

    node=(BST *)malloc(sizeof(BST));
    if(!node)
      return NULL;

    node->data = data;
    node->left=NULL;
    node->right=NULL;

    return node;
}

BST *Insert(BST *root,int d,int l)
{
    if(root==NULL)
      return(newNode(d));

    else
    {
        if(d < root->data)
           root->left=Insert(root->left,d,++l);
        else
           root->right=Insert(root->right,d,++l);

        return(root);
    }   
}


BST* CreateTree(BST *root1)
{
    int i=0;

    for(i=0;i<no_of_nodes;i++)
    {
      root1=Insert(root1,A[i],1);
    }

    return(root1);
}

void Inorder(BST *root1)
{
    if(root1==NULL)
        return;

    Inorder(root1->left);
    printf(" %3d ", root1->data);
    Inorder(root1->right);
}

void Preorder(BST *root1)
{
    if(root1==NULL)
        return;

    printf(" %3d ", root1->data);
    Preorder(root1->left);
    Preorder(root1->right);
}

void PrintArr(int *arr,int len)
{
    static int pathNo=0;
    int i;

    printf("\nPath %d ->",++pathNo);

    for(i=0;i<len;i++)
        printf(" %d ",arr[i]);

    return;
}

void PrintR2LPaths(BST *root,int pathArr[],int pathLen)
{
    if(root==NULL)
      return;

    pathArr[pathLen]=root->data;
    pathLen++;

    if(root->left==NULL && root->right==NULL)
    {
        PrintArr(pathArr,pathLen);
        return;
    }
    else
    {
        PrintR2LPaths(root->left,pathArr,pathLen);
        PrintR2LPaths(root->right,pathArr,pathLen);
    }
}

int main()
{
    int result=0;
    BST *root1=NULL;
    int pathArr[SIZE];

    root1=CreateTree(root1);

    printf("\n\n---------------------------------------------------\n");

    printf("\n\nPreorder Traversal of Tree : ");
    Preorder(root1);

    printf("\n\nInorder Traversal of Tree  : ");
    Inorder(root1);

    printf("\n\n---------------------------------------------------\n");

    printf("\nPrinting Paths\n\n");
    PrintR2LPaths(root1,pathArr,0);

    printf("\n\n---------------------------------------------------\n");
    getchar();

    return(0);
}

Answer 2

As you build your tree, be sure to initialize leftChild and rightChild to NULL (0) on your nodes. This is critical for leaf-nodes and for nodes missing either a leftChild or a rightChild.

class Node
      : leftChild(0)
      , rightChild(0)
      , data(0)
{
   Node* leftChild; 
   Node* rightChild; 
   char data;
}