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
Problem: 144. Binary Tree Preorder Traversal
Problem Link: leetcode.com/problems/binary-tree-preorder-traversal/
Companies Asked: Adobe, Google
Approach:
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.
Initiate a vector, ans to store the answer.
Write a recursive function whose parameters are TreeNode * root, vector<int> & ans.
While traversing check if the root becomes NULL then return calling from the function.
If not push the root->val into the ans.
Recall the same function with the Left node.
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;
}
};