✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-083

Preorder Traversal

Preorder traversal is a depth-first binary-tree traversal that processes the root node before recursively visiting the left and right subtrees. Its order is Root, Left, Right.

Explanation

Overview

Preorder traversal is a tree traversal algorithm in which the current node is processed first, followed by its left subtree and then its right subtree.

Key concepts

name: Core idea; description: The central focus of preorder traversal is the capability described here: Preorder traversal is a depth-first binary-tree traversal that processes the root node before recursively visiting the left and right subtrees. Its order is Root, Left, Right.; name: Problem context; description: Preorder Traversal is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using preorder traversal, check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

O(n), because every node is visited exactly once.

Space complexity

O(h) auxiliary space for a recursive implementation, where h is the tree height. An iterative implementation also requires a stack whose size depends on the tree structure.

Pseudocode

PREORDER(node):
if node == null:
return
VISIT(node)
PREORDER(node.left)
PREORDER(node.right)

Applications

Creating a copy of a tree.; Serializing a tree when null-child markers are included.; Generating prefix notation from expression trees.; Processing hierarchical structures from parent to children.; Producing directory listings in a parent-first order.

Limitations

The suitability of preorder traversal depends on the exact problem requirements and the assumptions made about the input.; An implementation of preorder traversal can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For preorder traversal, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Example or application

A worked example has not yet been added.

Definition

Preorder traversal is a tree traversal algorithm in which the current node is processed first, followed by its left subtree and then its right subtree.

Traversal Order

  • Root

  • Left Subtree

  • Right Subtree

Algorithm

  • Start at the root node.

  • If the current node is null, return.

  • Process or record the current node's value.

  • Recursively traverse the left child.

  • Recursively traverse the right child.

Pseudocode

PREORDER(node):
if node == null:
return
VISIT(node)
PREORDER(node.left)
PREORDER(node.right)

Example Tree

Root

A

Left

Root

B

Left

D

Right

E

Right

Root

C

Left

F

Right

G

Example Result

  • A

  • B

  • D

  • E

  • C

  • F

  • G

Step By Step

  • Visit A, the root.

  • Move to the left subtree and visit B.

  • Visit B's left child D.

  • Visit B's right child E.

  • Return to A and visit the right subtree rooted at C.

  • Visit C's left child F.

  • Visit C's right child G.

Iterative Implementation

Preorder can be implemented using an explicit stack. Push the root first, then repeatedly pop and visit a node. Push its right child before its left child so that the left child is processed first.

Recursive Implementation

The recursive implementation uses the function call stack to remember the current node while processing its left and right subtrees.

Time Complexity

O(n), because every node is visited exactly once.

Space Complexity

O(h) auxiliary space for a recursive implementation, where h is the tree height. An iterative implementation also requires a stack whose size depends on the tree structure.

Applications

  • Creating a copy of a tree.

  • Serializing a tree when null-child markers are included.

  • Generating prefix notation from expression trees.

  • Processing hierarchical structures from parent to children.

  • Producing directory listings in a parent-first order.

Common Mistakes

  • Visiting the left subtree before processing the root.

  • Pushing the left child before the right child in a LIFO iterative implementation.

  • Forgetting the null-node base case.

  • Assuming preorder output is sorted for an arbitrary binary tree.

Important Distinction

Preorder processes the root before its descendants. Inorder processes the root between its left and right subtrees, while postorder processes it after both subtrees.

Key Concepts

NameDescription

Core idea

The central focus of preorder traversal is the capability described here: Preorder traversal is a depth-first binary-tree traversal that processes the root node before recursively visiting the left and right subtrees. Its order is Root, Left, Right.

Problem context

Preorder Traversal is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using preorder traversal, check its assumptions, input requirements, expected output, and resource constraints.

Limitations

  • The suitability of preorder traversal depends on the exact problem requirements and the assumptions made about the input.

  • An implementation of preorder traversal can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For preorder traversal, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Practice Questions

QuestionAnswer

What is the main purpose of preorder traversal?

Preorder traversal is a depth-first binary-tree traversal that processes the root node before recursively visiting the left and right subtrees. Its order is Root, Left, Right.

What should be checked before applying preorder traversal?

For preorder traversal, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of preorder traversal be validated?

Trace a representative preorder traversal case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of preorder traversal.

  • Identify the assumptions, inputs, and conditions relevant to preorder traversal.

  • Evaluate an application of preorder traversal for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures