Print all the root to leaf paths in a binary tree: wrong output

Question

I am trying to solve the question:

Given a binary tree, print all the root to leaf paths.

I think I have understood the logic that I need to implement, but my code it is not giving the desired output.

Example

For this tree:

           1
         /   \
        2     3
       / \   / \
      4   5 6   7

The expected output is:

But my code outputs this:

Code

My C++ code below:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

vector <int> ans;

struct node* newnode(int data)
{
    struct node* temp=(struct node*)malloc(sizeof(struct node));

    temp->data=data;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

void root_to_leaf_path(struct node* root)
{
    if(root==NULL)
        return;
    root_to_leaf_path(root->left);
    ans.push_back(root->data);
    if(root->left==NULL && root->right==NULL)
    {
        int n=ans.size();
        for(int i=0;i<n;i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    root_to_leaf_path(root->right);
    ans.pop_back();
}

int main()
{
    struct node* root=newnode(1);
    struct node* p1=newnode(2);
    struct node* p2=newnode(3);
    struct node* p3=newnode(4);
    struct node* p4=newnode(5);
    struct node* p5=newnode(6);
    struct node* p6=newnode(7);

    root->left=p1;
    root->right=p2;
    p1->left=p3;
    p1->right=p4;
    p2->left=p5;
    p2->right=p6;
    root_to_leaf_path(root);
}

Where is the mistake?

To start with, you're missing a bunch of `<>`. `#include iostream` should be `#include `, same with the other inclusions. `vector int ans;` should be `vector ans;`. — Nathan Pierson, Jan 13 '22 at 06:45
actually in real code I have written it but while posting it on stack overflow <> symbols got disappered . So real problem is something else — ABHIRAJ RAM, Jan 13 '22 at 07:50
Please correct that by editing your question, before we continue. — trincot, Jan 13 '22 at 08:01
@ABHIRAJRAM `struct node* temp=(struct node*)malloc(sizeof(struct node));` -- Are you reading `C` books instead of `C++` books? 1) There is no need for `struct` here. 2) Why are you using `malloc` instead of `new`? — PaulMcKenzie, Jan 13 '22 at 08:02
actually my college is teaching C and I am learning C++ due to this there is mixing of language. But my code is not giving any compile time error but the output which is being displayed is wrong. My code's output is 4 2 5 1 6 1 3 7 — ABHIRAJ RAM, Jan 13 '22 at 08:11
@ABHIRAJRAM C and C++ are two separate languages. If you keep using `C`-style idioms in C++, you will not learn C++ properly and/or run across issues with compiling and running the code. Also -- *I am searching for what mistake I have done in my code* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Jan 13 '22 at 13:56
Aren't you going to edit and correct the syntax issues? Some effort is expected from your side. — trincot, Jan 13 '22 at 20:31
@trincot I have edited and corrected the syntax issue , but not getting the correct output — ABHIRAJ RAM, Jan 14 '22 at 06:20
@Nathan Pierson the desired output is 1 2 4, 1 2 5, 1 3 6, 1 3 7 but insted I was getting 4 2, 5 1 6, 1 3 7, — ABHIRAJ RAM, Jan 14 '22 at 06:29
Can you explain why you call `root_to_leaf_path(root->left)` before `ans.push_back(root->data)`? How will the left child be able to print its parent? — Nathan Pierson, Jan 14 '22 at 06:34
@Nathan Pierson , thanks a lot ,you are right I understood my mistake ans.push_back should come first , now it is giving correct ans. Thanks again for giving me your valuable time ☺️ — ABHIRAJ RAM, Jan 14 '22 at 06:40

score 0 · Answer 1 · answered Jan 14 '22 at 06:39

As can be seen in the output you got, the root is not output first. This happens because your code first makes a recursive call and only then pushes a value to the vector. This means that the deepest value will be pushed first.

You should push the value to the vector before making a recursive call: that way the values will accumulate as you walk down the tree.

So change this:

root_to_leaf_path(root->left);
ans.push_back(root->data);

to this:

ans.push_back(root->data);
root_to_leaf_path(root->left);

Print all the root to leaf paths in a binary tree: wrong output

Example

Code

1 Answers1