Return the preorder traversal of a binary tree: visit the root first, then the left subtree, then the right subtree.
Given the root of a binary tree, return the values of its nodes in preorder traversal.
In preorder traversal, each node is processed before its children. The visit order is:
- Current node
- Left subtree
- Right subtree
You may solve this using either recursion or an explicit stack.
Input Format
- A binary tree root node is provided as the input.
- Each node contains an integer value and references to its left and right children.
- The tree may be empty.
Output Format
- Return an array/list of integers representing the preorder traversal.
- If the tree is empty, return an empty array/list.
Constraints
- The number of nodes is in the range for a typical interview setting.
- Node values are integers.
- The tree structure is valid and acyclic.
Note: Exact platform constraints may vary.
Example 1
Input
root = [1,null,2,3]
Output
[1,2,3]
Explanation
Visit 1 first, then move to the right subtree rooted at 2, and then visit 3.
Example 2
Input
root = [1,2,3,4,5]
Output
[1,2,4,5,3]
Explanation
Preorder visits the root, then recursively the entire left subtree, then the entire right subtree.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.