Binary Tree Preorder Traversal

Given the root of a binary tree, return a list containing the values of the tree nodes in preorder traversal order. Preorder traversal involves visiting the root node first, then recursively traversing the left subtree, and finally recursively traversing the right subtree. This traversal method is useful for creating copies of trees and for certain tree-based algorithms.

Problem Description

You are tasked with implementing a function that performs a preorder traversal of a binary tree. The binary tree is represented as a tree data structure where each node has a value, a left child, and a right child. Your function should return a list containing the values of the nodes in the order they are visited during the preorder traversal.

What needs to be achieved:

• Implement a function that takes the root node of a binary tree as input.
• Perform a preorder traversal of the tree.
• Return a list containing the node values in the order they were visited.

Key Requirements:

• The function must handle empty trees gracefully (i.e., when the root is null or None).
• The traversal must follow the preorder order: Root -> Left -> Right.
• The returned list should contain the node values in the correct order.

Expected Behavior:

The function should return an empty list if the input tree is empty. For non-empty trees, the list should contain the values of the nodes in preorder traversal order.

Edge Cases to Consider:

• Empty tree (root is null or None).
• Tree with only a root node.
• Skewed trees (left-skewed or right-skewed).
• Trees with varying depths.

Examples

Example 1:

Input:
    1
   / \
  2   3

Output: [1, 2, 3] Explanation: The preorder traversal starts at the root (1), then visits the left subtree (2), and finally the right subtree (3).

Example 2:

Input:
    1
   / \
  2   null
 / \
3   4

Output: [1, 2, 3, 4] Explanation: The preorder traversal starts at the root (1), then visits the left subtree (2), which has left child (3) and right child (4).

Example 3:

Input: null
Output: []
Explanation: An empty tree results in an empty list.

Constraints

• The number of nodes in the tree can range from 0 to 1000.
• The values of the nodes are integers.
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree.
• The solution should have a space complexity of O(H), where H is the height of the tree (due to the recursion stack). In the worst case (skewed tree), H can be N.

Notes

Consider using recursion to implement the preorder traversal. Think about the base case for the recursion (when to stop). You'll need to maintain a list to store the visited node values in the correct order. The key is to process the current node before recursively processing its children.