Implement preorder traversal

Summary

Write a function to perform a preorder (root-left-right) traversal of a binary tree and return the list of visited node values.

Problem statement

Given the root of a binary tree, implement a function preorder(root) that returns a list of node values visited in preorder (root, left, right). The tree nodes are represented by the provided Node class. The function should handle empty trees (None) and return an empty list for them.

Task

Implement preorder traversal that visits root then left subtree then right subtree. Return values as a list in traversal order.

Examples

Input format

A single argument: root (Node or None).

Output format

A list of integers representing node values in preorder order.

Constraints

Tree node count <= 10^4. Node values are integers. Use recursion or iteration. Do not print; return the list.

Samples