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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<int> PreorderTraversal(TreeNode root) {
13 List<int> res = new List<int>();
14 Preorder(root, res);
15 return res;
16 }
17
18 private void Preorder(TreeNode node, List<int> res) {
19 if (node == null) return;
20 res.Add(node.val);
21 Preorder(node.left, res);
22 Preorder(node.right, res);
23 }
24}This C# script defines a TreeNode class and a solution class with a PreorderTraversal method. It uses recursion to populate a List with the preorder sequence.
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.