-1

I'm doing a leetcode problem which you can check it here:https://leetcode.com/problems/binary-tree-preorder-traversal here's my first time answer which is a wrong answer:

class Solution {
public:
    TreeNode* preorderTraversal(TreeNode* root, vector<int> &res){
        if(root) res.push_back(root->val); else return nullptr;
        if(root->left) return preorderTraversal(root->left,res);
        if(root->right) return preorderTraversal(root->right,res);
        return root;
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderTraversal(root,res);
        return res;
    }
};

And here's my second time answer which passed the test:

class Solution {
public:
    void preorderTraversal(TreeNode* root, vector<int> &res){
        if(root) res.push_back(root->val); else return;
        preorderTraversal(root->left,res);
        preorderTraversal(root->right,res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderTraversal(root,res);
        return res;
    }
};

if you had a leetcode account you can simply click the link above and copy my two answers in the code area and run each of both, you can then find out that inputs like "[1,2,3]", which represent trees that only have left branches in every tree node, can only pass the second code while in the first one, the left most node's value(in this example, 3) is not included in the vector that the problem ask for. I wonder what's wrong with my first answer that caused the difference in result.

I know the first code seem weird and tedious, I just wonder why it can't work correcetly.

I'll be really thankful to you guys who help me out.

noob
  • 13
  • 3
  • 2
    What do you think happens after you return in the `if(root->left)` conditional? (And what is the point of returning any value at all?) – molbdnilo Apr 28 '22 at 13:43
  • *of these two almost same answers* -- They are not "almost same answers", because both sets of code produce different results. You have the wrong belief that because code "looks similar" means they should act the same way. – PaulMcKenzie Apr 28 '22 at 13:51
  • Of course I know similar codes can result very differently, Maybe my brain's just not functioning after a day's study. By the way the design of the return value is just my first thought so I followed it and write the code down, so confusing. Let's say it's such a stupid design. – noob Apr 28 '22 at 14:21
  • 1
    @noob *if you had a leetcode account* -- There is no need for an account. You should have done this yourself, just like [this example](http://coliru.stacked-crooked.com/a/bf50e32eed00e9f8) by simply creating a [mcve] of your test, instantiating a `Solution` object, and providing it with the data you are claiming works differently. Then you could have [debugged](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) the code. – PaulMcKenzie Apr 28 '22 at 14:30
  • @PaulMcKenzie You're right, there are so much I can do to debug the code myself. Maybe I'm just lazy-minded now and not willing to think by myself. The reason I mentioned the account is that the link above is a leetcode link and the problem description is in it. And in case someone wanted to run my code to see what I mean(I'm not sure if I made it clear), I want to show the exactly same problem I ran into to him. But yeah, I should've done it myself. Anyway, thank you for teaching me so much about coding, I'll follow your guide in my future programming career. – noob Apr 28 '22 at 14:53

1 Answers1

2

Preorder traversal requires to visit all the nodes in the tree.

In your 1st version you have these lines:

if(root->left) return preorderTraversal(root->left,res);
if(root->right) return preorderTraversal(root->right,res);

If root->left is not null the return statement will be executed, and will cause the function's execution to end after the recursive call to preorderTraversal will return.

This means that if root->left is not null the whole right sub tree will not be visited.

The second if is also wrong for consistency reasons (no reason the return the right subtree if you should never return the left one).

Your 2nd version performs recursion both to the left and to the right (in that order) which ensures all the nodes are visited according to the preorder criterion.

wohlstad
  • 12,661
  • 10
  • 26
  • 39
  • Stupid me. But even though the right sub tree will not be reached, the value of the last node visited in the left sub tree should be included in the vector, but just like the example"[1,2,3]", 3 wasn't in the answer. How could it be cause the value "2" is not null so the value "3" node ought to have been visited as the very first line of the preorderTraversal should be executed at very first before any return statement. – noob Apr 28 '22 at 14:12
  • Not sure I understand what you mean. You can try to debug this scenario (I don't have access to the environment). Just looking at your code it seems like if the tree has only left chilren all the way, even your 1st method will traverse it correctly. But better trust the debugger than my eyes. – wohlstad Apr 28 '22 at 14:18
  • That's exactly what I mean,. The code seems to work well if the tree has only left children all the way, but indeed it doesn't. Just as I described, "[1,2,3]" should be such kind of tree, but the value "3" seems not to be included in the vector, as if the node of it is not visited at all. I'm so confused. Anyway, thank you for pointing out the problem in my first code, I'll try debugging it later probably. – noob Apr 28 '22 at 14:30
  • 1
    @noob -- See my comment in the main section about debugging your code. – PaulMcKenzie Apr 28 '22 at 14:32