top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

print root to leaf node with recursion

+4 votes
70 views

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

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

posted Jul 3, 2016 by Shahsikant Dwivedi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote
 
Best answer

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 by Shivam Kumar Pandey
thanks Shashikant for selecting as best ans
Similar Questions
+2 votes

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.

+4 votes

Addition to this,

Can we consider "a car a man a maraca" as palindrome string?
Click here To see similar kind of palindrome strings,
Are they really a palindrome?

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...