CODEWITHSUNDEEP
c++
user8177388
user8177388

Reputation:

Regarding preorder tree traversal

I have written the following code snippet for recursive Binary Tree Preorder Traversal:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    std::vector<int> myVec;
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==NULL)
            return vector<int>();

        myVec.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);

        return myVec;
    }
};

While this code runs and produces the expected output, I am not totally sure if this is correct; because when I call preorderTraversal(root->left); and preorderTraversal(root->right); I am not using the values that they return (vector<int>s). So,

  1. Is this correct?
  2. If no, then how can I rectify this code?

Upvotes: 2

Views: 941

Answers (1)

alexeykuzmin0
alexeykuzmin0

Reputation: 6440

Yes, it is correct if you call it once. If not, myVec vector is not cleared.

In fact, each call to preorderTraversal, except the top one and path from it to the left, return some intermediate state which doesn't make much sense. If I were you, I would refactor this code to hide the intermediate value inside the class:

class Solution {
private:
    std::vector<int> myVec;

    void traverse(TreeNode* root) {
        if (root == NULL)
            return;

        myVec.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        myVec.clear();
        traverse(root);
        return myVec;
    }
};

Upvotes: 3

Related Questions