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 <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10void preorder(struct TreeNode* root, int* result, int* count) {
11 if (root == NULL) return;
12 result[(*count)++] = root->val;
13 preorder(root->left, result, count);
14 preorder(root->right, result, count);
15}
16
17int* preorderTraversal(struct TreeNode* root, int* returnSize) {
18 int* result = (int*)malloc(100 * sizeof(int));
19 *returnSize = 0;
20 preorder(root, result, returnSize);
21 return result;
22}This C code defines a recursive function for the preorder traversal. It allocates space for the result and uses a helper function to populate the preorder values by traversing each node recursively.
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#include
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.