Tree traversal Algorithms

Tree traversal algorithms play a crucial role in various applications, including parsing expressions, generating sorted lists, and searching for elements in binary search trees. Understanding different traversal techniques is essential for efficient tree manipulation and processing.

Three main types of tree traversal algorithms exist:

Preorder Traversal: Visit the current node before its children.
Inorder Traversal: Visit the left subtree, then the current node, and finally the right subtree.
Postorder Traversal: Visit the children of a node before the node itself.

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

function preorderTraversal(root, result = []) {
    if (root) {
        result.push(root.value);
        preorderTraversal(root.left, result);
        preorderTraversal(root.right, result);
    }
    return result;
}

function inorderTraversal(root, result = []) {
    if (root) {
        inorderTraversal(root.left, result);
        result.push(root.value);
        inorderTraversal(root.right, result);
    }
    return result;
}

function postorderTraversal(root, result = []) {
    if (root) {
        postorderTraversal(root.left, result);
        postorderTraversal(root.right, result);
        result.push(root.value);
    }
    return result;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log("Preorder Traversal:", preorderTraversal(root)); // Output: [1, 2, 4, 5, 3]
console.log("Inorder Traversal:", inorderTraversal(root));   // Output: [4, 2, 5, 1, 3]
console.log("Postorder Traversal:", postorderTraversal(root)); // Output: [4, 5, 2, 3, 1]

The time complexity of tree traversal algorithms is O(n), where n is the number of nodes in the tree. Each node is visited exactly once during traversal, resulting in linear time complexity.

Tree traversal algorithms are essential tools for navigating and processing tree structures efficiently. By mastering the Preorder, Inorder, and Postorder traversal techniques and understanding their implementations in JavaScript, developers can effectively manipulate and analyze tree-based data structures in various applications.