Problem Statement:
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Examples:
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Initialize an empty array
ansto store the result. - Define a helper function
traversal(curr)that:- Returns if the
current node is null. - Pushes the current node’s value to ans.
- Recursively calls itself on the left and then right child.
- Returns if the
- Call
traversal(root)to start the traversal from the root. - Return the ans array containing the preorder traversal.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
ans = []
Start traversal(root = 1)
→ curr = 1 → ans.push(1) → ans = [1]
→ traversal(curr.left = 2)
→ curr = 2 → ans.push(2) → ans = [1, 2]
→ traversal(curr.left = null) → return
→ traversal(curr.right = 4)
→ curr = 4 → ans.push(4) → ans = [1, 2, 4]
→ traversal(curr.left = null) → return
→ traversal(curr.right = null) → return
← return to curr = 2 → done
← return to curr = 1
→ traversal(curr.right = 3)
→ curr = 3 → ans.push(3) → ans = [1, 2, 4, 3]
→ traversal(curr.left = null) → return
→ traversal(curr.right = null) → return
← return to curr = 1 → done
Traversal complete.
Final ans = [1, 2, 4, 3]
Output: Result: [1, 2, 4, 3]
var preorderTraversal = function(root) {
let ans = [];
function traversal(curr){
if(!curr) return;
ans.push(curr.val);
traversal(curr.left);
traversal(curr.right);
}
traversal(root);
return ans;
};
class Solution:
def preorderTraversal(self, root):
ans = []
def traversal(curr):
if not curr:
return
ans.append(curr.val)
traversal(curr.left)
traversal(curr.right)
traversal(root)
return ans
class Solution {
public void traversal(TreeNode curr, List ans) {
if (curr == null) return;
ans.add(curr.val);
traversal(curr.left, ans);
traversal(curr.right, ans);
}
public List preorderTraversal(TreeNode root) {
List ans = new ArrayList<>();
traversal(root, ans);
return ans;
}
}
class Solution {
public:
void traversal(TreeNode* curr, vector& ans) {
if (!curr) return;
ans.push_back(curr->val);
traversal(curr->left, ans);
traversal(curr->right, ans);
}
vector preorderTraversal(TreeNode* root) {
vector ans;
traversal(root, ans);
return ans;
}
};
void traversal(struct TreeNode* curr, int* ans, int* idx) {
if (!curr) return;
ans[(*idx)++] = curr->val;
traversal(curr->left, ans, idx);
traversal(curr->right, ans, idx);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int* ans = malloc(1000 * sizeof(int));
*returnSize = 0;
traversal(root, ans, returnSize);
return ans;
}
public class Solution {
public void Traversal(TreeNode curr, List ans) {
if (curr == null) return;
ans.Add(curr.val);
Traversal(curr.left, ans);
Traversal(curr.right, ans);
}
public IList PreorderTraversal(TreeNode root) {
List ans = new List();
Traversal(root, ans);
return ans;
}
}
