preorder

Preorder is a term used in several disciplines with distinct meanings. In mathematics and related fields, a preorder (also called a quasiorder) is a binary relation that is reflexive and transitive. It may fail to be antisymmetric, in which case distinct elements can be mutually related. Preorders generalize partial orders and often arise in the study of equivalence relations and order structure. For example, the relation “is less than or equal to” on real numbers is a preorder and a total order, while other preorder relations relax antisymmetry.

In computer science, preorder refers to a specific depth-first traversal order of a tree. In a preorder traversal, the value at the current node is processed before its children, which are then traversed recursively in a defined order (often left to right). This contrasts with inorder and postorder traversals. Preorder traversal runs in linear time with respect to the number of nodes, O(n), and uses O(h) space on the call stack or an explicit stack, where h is the tree height. It is commonly used for tasks such as copying trees, generating prefix notation, or evaluating expression trees.

In commerce, a preorder is an arrangement to obtain a product before it is released or stocked. Customers may pay in advance or place a reservation, and shipments typically occur when the producer completes production or fulfills preorders. Preorder terms vary by retailer and product, including deadlines, guarantees, and cancellation policies.

See also: postorder, inorder, depth-first search, partial order, quasiorder.