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
- If the tree is empty (
rootis null), return an empty array. - Initialize a stack with the root node and an empty result array
ans. - While the stack is not empty:
- Pop the top node from the stack and add its value to
ans. - Push the right child first, then the left child (if they exist), so the left child is processed first.
- Pop the top node from the stack and add its value to
- Return the result array
ans.
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 = []
stack = [1]
Iteration 1:
→ stack = [1]
→ curr = stack.pop() = 1
→ ans.push(1) → ans = [1]
→ push(curr.right = 3) → stack = [3]
→ push(curr.left = 2) → stack = [3, 2]
Iteration 2:
→ stack = [3, 2]
→ curr = stack.pop() = 2
→ ans.push(2) → ans = [1, 2]
→ push(curr.right = 4) → stack = [3, 4]
→ curr.left = null → do nothing
Iteration 3:
→ stack = [3, 4]
→ curr = stack.pop() = 4
→ ans.push(4) → ans = [1, 2, 4]
→ curr.right = null → do nothing
→ curr.left = null → do nothing
Iteration 4:
→ stack = [3]
→ curr = stack.pop() = 3
→ ans.push(3) → ans = [1, 2, 4, 3]
→ curr.right = null → do nothing
→ curr.left = null → do nothing
stack = [] → done
Traversal complete.
Final ans = [1, 2, 4, 3]
Output: Result: [1, 2, 4, 3]
var preorderTraversal = function(root) {
if(!root) return [];
let ans = [];
let stack = [root];
while(stack.length) {
let curr = stack.pop();
ans.push(curr.val);
curr.right && stack.push(curr.right);
curr.left && stack.push(curr.left);
}
return ans;
}
def preorderTraversal(root):
if not root:
return []
ans = []
stack = [root]
while stack:
curr = stack.pop()
ans.append(curr.val)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return ans
public List preorderTraversal(TreeNode root) {
if (root == null) return new ArrayList<>();
List ans = new ArrayList<>();
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
ans.add(curr.val);
if (curr.right != null) stack.push(curr.right);
if (curr.left != null) stack.push(curr.left);
}
return ans;
}
vector preorderTraversal(TreeNode* root) {
if (!root) return {};
vector ans;
stack s;
s.push(root);
while (!s.empty()) {
TreeNode* curr = s.top(); s.pop();
ans.push_back(curr->val);
if (curr->right) s.push(curr->right);
if (curr->left) s.push(curr->left);
}
return ans;
}
void traversal(struct TreeNode* curr, int* ans, int* idx) {
// Assuming TreeNode is defined as:
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
if (!root) {
*returnSize = 0;
return NULL;
}
struct TreeNode* stack[1000];
int* ans = malloc(sizeof(int) * 1000);
int top = -1, idx = 0;
stack[++top] = root;
while (top >= 0) {
struct TreeNode* curr = stack[top--];
ans[idx++] = curr->val;
if (curr->right) stack[++top] = curr->right;
if (curr->left) stack[++top] = curr->left;
}
*returnSize = idx;
return ans;
}
public IList PreorderTraversal(TreeNode root) {
if (root == null) return new List();
List ans = new List();
Stack stack = new Stack();
stack.Push(root);
while (stack.Count > 0) {
TreeNode curr = stack.Pop();
ans.Add(curr.val);
if (curr.right != null) stack.Push(curr.right);
if (curr.left != null) stack.Push(curr.left);
}
return ans;
}
