hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Binary Tree Preorder Traversal


  • Approach:

    1. The basic approach to traverse a tree in a pre-order fashion - Root, Left, Right. That means processing the Root node first. Then go for the Left node and then for the Right node.

    2. Initiate a vector, ans to store the answer.

    3. Write a recursive function whose parameters are TreeNode * root, vector<int> & ans.

    4. While traversing check if the root becomes NULL then return calling from the function.

    5. If not push the root->val into the ans.

    6. Recall the same function with the Left node.

    7. Recall the same function with the Right node.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N) + Stack Usage


Code [C++]

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:


void traversePreOrder(TreeNode * root, vector<int>& ans){

if(!root) return;

ans.push_back(root->val);

traversePreOrder(root->left, ans);

traversePreOrder(root->right, ans);

}


vector<int> preorderTraversal(TreeNode* root) {

vector<int>ans;

traversePreOrder(root, ans);

return ans;

}

};