Sponsored
Sponsored
The recursive approach naturally aligns with the definition of preorder traversal: visit the root first, then recursively traverse the left subtree, followed by the right subtree.
Time Complexity: O(N) where N is the number of nodes, as each node is visited once. Space Complexity: O(N) in the worst case due to recursion stack space.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12void preorder(TreeNode* root, vector<int>& res) {
13 if (!root) return;
14 res.push_back(root->val);
15 preorder(root->left, res);
16 preorder(root->right, res);
17}
18
19vector<int> preorderTraversal(TreeNode* root) {
20 vector<int> res;
21 preorder(root, res);
22 return res;
23}This C++ implementation uses a vector to store the traversal results. A helper function performs the recursive preorder traversal, ensuring that each node's value is recorded correctly.
The iterative approach replaces the recursive call stack with an explicit stack. Nodes are processed in preorder, using a stack to maintain traversal state.
Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes.
1#
In C, we use an array to simulate a stack, manually pushing and popping nodes while traversing the tree. Nodes are visited and added to the result list in prenode order.