Binary Trees - Preorder Traversal

Preorder traversal technique follows the Root -> Left -> Right order.

Preorder traversal is another method for visiting all the nodes in a binary tree. The recursive approach is similar to that of inorder traversal, with the key difference being the order in which nodes are processed. In preorder traversal, the root node is processed first, followed by the left subtree, and then the right subtree.

Algorithm:

1. Visit the current root node
2. Treverse the left subtree (recursively).
3. Treverse the right subtree (recursively).

So, the current node is processed first, followed by a traversal of the left subtree. Once all the nodes in the left subtree are processed, the traversal then moves to the right subtree.

Characteristics of Preorder Traversal

• Preorder traversal is useful in creating a copy of tree. It is also used to create the prefix expressions of an expression tree.
• Time Complexity: Preorder traversal of a tree with 𝑛 nodes takes 𝑂(𝑛) time, as it visits each node exactly once.

Compare with other traversal algorithms

Inorder Traversal: Left -> Root -> Right

Postorder Traversal: Left -> Right -> Root

Solution & Visualize:

The animation/visualization below demonstrates how the Preorder traversal works.

function preOrderTraversal(root) {
    if (root !== null) {
        console.log(root.data);

        preOrderTraversal(root.left);

        preOrderTraversal(root.right);
    }
}

const nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
const root = buildTree(nodes);

preOrderTraversal(root);
                                        

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function buildTree(nodes, index, size) {
    if (index < size) {
        if (nodes[index] === null) {
            return null;
        }

        let root = new TreeNode(nodes[index]);
        root.left = buildTree(nodes, 2 * index + 1, size);
        root.right = buildTree(nodes, 2 * index + 2, size);

        return root;
    }

    return null;
}