print root to leaf node with recursion

Question

Given a binary tree, print all its root to leaf paths with recursion. For example, consider the following Binary Tree,

complexity must be O(n) or O(nlogn).

Answer 1

Hi Shashikant, Please use this code to get your required solution within time complexity O(n).
ideone.com link : https://ideone.com/wzTO3E

  /* Constructed binary tree is
                6
              /   \
            3      5
          /  \    /
         2     5  4
               /\
              7  4

      */

and here is c++ code :

#include<bits/stdc++.h>
using namespace std;

struct node
{
   int data;
   struct node* left;
   struct node* right;
};

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

void printPathsRecur(struct node* node, int path[], int pathLen) 
{
  if (node==NULL) 
    return;
  path[pathLen] = node->data;
  pathLen++;
  if (node->left==NULL && node->right==NULL) 
  {
    printArray(path, pathLen);
  }
  else
  {
    printPathsRecur(node->left, path, pathLen);
    printPathsRecur(node->right, path, pathLen);
  }
}
void printArray(int ints[], int len) 
{
  int i;
  for (i=0; i<len; i++) 
  {
    printf("%d ", ints[i]);
  }
  printf("\n");
}    
struct node* newnode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}
int main()
{ 

  /* Constructed binary tree is
            6
          /   \
        3      5
      /  \    /
     2     5  4
           /\
          7  4

  */

  struct node *root = newnode(6);
  root->left        = newnode(3);
  root->right       = newnode(5);
  root->left->left  = newnode(2);
  root->left->right = newnode(5);
  root->left->right->left=newnode(7);
  root->left->right->right=newnode(4);
  root->right->left = newnode(4);

  printPaths(root);

  getchar();
  return 0;
}

Comments

thanks Shashikant for selecting as best ans