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.
1function
JavaScript achieves preorder traversal iteratively using an array to simulate the stack. This approach offers flexibility and error resilience in managing deep trees.