# print root to leaf node with recursion

91 views

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).

posted Jul 3, 2016

+1 vote

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;
}
``````
answer Jul 3, 2016
thanks Shashikant for selecting as best ans
Similar Questions

Say you are given a tree and weight is calculated by sum of values in the nodes in that path.

+1 vote

Write a recursive function:

``````int sum( int x, int max )
{
/* complete the code */
}
``````

that calculates the sum of the numbers from x to max (inclusive). For example, sum (4, 7) would compute 4 + 5 + 6 + 7 and return the value 22.

Note: The function must be recursive.

Can we consider `"a car a man a maraca"` as palindrome string?