Pre-order Traversal in PHP: Recursive, Iterative, and Interactive Implementations

In computer science, a tree is an important data structure, and traversing a tree is a fundamental operation. Pre-order traversal is a common depth‑first method that visits nodes in the "root‑left‑right" order, useful for binary trees, expression trees, and more.

What is Pre-order Traversal?

Pre-order traversal follows the order:

Visit the root node first.

Recursively traverse the left subtree.

Recursively traverse the right subtree.

This traversal is valuable for copying tree structures, evaluating prefix expressions, and other scenarios.

Binary Tree Representation in PHP

In PHP, a binary tree node can be represented with a class:

class TreeNode {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}

Basic Pre-order Traversal Implementation

The recursive implementation is straightforward:

function preOrderTraversal($root) {
    if ($root != null) {
        echo $root->value . " "; // visit root
        preOrderTraversal($root->left);  // traverse left subtree
        preOrderTraversal($root->right); // traverse right subtree
    }
}

Interactive Input Implementation

An interactive PHP script can let users dynamically build a tree and view traversal results:

class InteractiveTree {
    private $root;

    public function __construct() {
        $this->root = null;
    }

    // Interactive tree construction
    public function buildTree() {
        echo "Let's build a binary tree!\n";
        $this->root = $this->buildNode();
    }

    private function buildNode() {
        echo "Enter node value (or 'null' for empty node): ";
        $value = trim(fgets(STDIN));
        if ($value === 'null' || $value === '') {
            return null;
        }
        $node = new TreeNode($value);
        echo "Add left child for node {$value}...\n";
        $node->left = $this->buildNode();
        echo "Add right child for node {$value}...\n";
        $node->right = $this->buildNode();
        return $node;
    }

    public function performPreOrder() {
        echo "Choose traversal method:\n";
        echo "1. Recursive implementation\n";
        echo "2. Non‑recursive implementation (using stack)\n";
        echo "Enter choice (1 or 2): ";
        $choice = trim(fgets(STDIN));
        echo "Pre-order traversal result: ";
        if ($choice == '1') {
            $this->preOrderRecursive($this->root);
        } else {
            $this->preOrderIterative($this->root);
        }
        echo "\n";
    }

    private function preOrderRecursive($node) {
        if ($node != null) {
            echo $node->value . " ";
            $this->preOrderRecursive($node->left);
            $this->preOrderRecursive($node->right);
        }
    }

    private function preOrderIterative($root) {
        if ($root == null) return;
        $stack = [];
        array_push($stack, $root);
        while (!empty($stack)) {
            $node = array_pop($stack);
            echo $node->value . " ";
            // Push right child first, then left child
            if ($node->right != null) array_push($stack, $node->right);
            if ($node->left != null) array_push($stack, $node->left);
        }
    }
}

// Main program
echo "PHP Pre-order Traversal Interactive Demo\n";
echo "------------------------\n";
$tree = new InteractiveTree();
$tree->buildTree();
while (true) {
    echo "\nOptions:\n";
    echo "1. Execute pre-order traversal\n";
    echo "2. Rebuild tree\n";
    echo "3. Exit\n";
    echo "Enter choice: ";
    $choice = trim(fgets(STDIN));
    switch ($choice) {
        case '1':
            $tree->performPreOrder();
            break;
        case '2':
            $tree->buildTree();
            break;
        case '3':
            exit("Program terminated.\n");
        default:
            echo "Invalid choice, please try again.\n";
    }
}

Non-recursive Implementation (Using Stack)

Recursive methods are concise but may cause stack overflow on large trees. The stack‑based iterative version avoids this:

function preOrderIterative($root) {
    if ($root == null) return;
    $stack = [];
    array_push($stack, $root);
    while (!empty($stack)) {
        $node = array_pop($stack);
        echo $node->value . " ";
        // Right child is pushed first so that left child is processed first
        if ($node->right != null) array_push($stack, $node->right);
        if ($node->left != null) array_push($stack, $node->left);
    }
}

Practical Application Examples

Pre-order traversal is used in various real‑world scenarios:

Expression‑tree evaluation: the prefix (Polish) notation is the result of a pre-order traversal.

Directory‑structure copying: create the root directory first, then process sub‑directories.

Serializing a tree structure into a string representation.

Complete Interactive Example Code

The full script combining all the pieces is shown above.

How to Run

Save the code to a file named preorder_traversal.php .

Execute it from the command line with php preorder_traversal.php .

Follow the prompts to input the tree structure and choose operations.

Conclusion

Through this article you have learned:

The basic concept and visit order of pre-order traversal.

Recursive and non‑recursive implementations of pre-order traversal in PHP.

How to create an interactive program to dynamically build a tree and test traversal results.

Mastering pre-order traversal lays a solid foundation for more advanced tree algorithms such as in‑order, post‑order traversals, or depth‑first search. Consider extending the code with visualizations or additional traversal methods to deepen your understanding.

Java learning resources

C language learning resources

Frontend learning resources

C++ learning resources

PHP learning resources