In Preorder Tree Traversal, the order of accessing node is Node -> Left Subtree -> Right Subtree.
Code
1. Recursive Approch – 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> A, B, C; if(root) { A.push_back(root->val); B = preorderTraversal(root->left); C = preorderTraversal(root->right); A.insert(A.end(), B.begin(), B.end()); A.insert(A.end(), C.begin(), C.end()); } return A; } }; |
2. Recursive Approch – 2 (Using global variable)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: vector<int> A; vector<int> preorderTraversal(TreeNode* root) { if(root) { A.push_back(root->val); preorderTraversal(root->left); preorderTraversal(root->right); } return A; } }; |
3. Recursive Approch – 3 (Using pass by reference)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: void helper(TreeNode* root, vector<int> &A) { if(root) { A.push_back(root->val); helper(root->left, A); helper(root->right, A); } } vector<int> preorderTraversal(TreeNode* root) { vector<int> A; helper(root, A); return A; } }; |
4. Iterative Approch – 1 (Using Stack)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> A; stack<TreeNode*> st; while(1) { while(root) { A.push_back(root->val); st.push(root); root = root->left; } if(st.empty()) break; else { root = st.top(); st.pop(); root = root->right; } } return A; } }; |
5. Iterative Approch – 2 (Without Stack Using Morris Traversal)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> A; TreeNode* curr = root; while(curr) { if(!curr->left) { A.push_back(curr->val); curr = curr->right; }else { TreeNode* pred = curr->left; while(pred->right != nullptr && pred->right != curr) { pred = pred->right; } if(pred->right == curr){ pred->right = nullptr; curr = curr->right; }else { A.push_back(curr->val); pred->right = curr; curr = curr->left; } } } return A; } }; |
To execute Preorder tree traversal Program : https://leetcode.com/problems/binary-tree-preorder-traversal
References:
Recent Comments