Tree traversal involves visiting all nodes of a tree data structure in a systematic way. There are different methods for tree traversal: depth-first (pre-order, in-order, post-order) and breadth-first traversal. Here's an explanation of each along with JavaScript code examples:
Depth-First Traversal:
-
Pre-order Traversal:
- Visit the current node, then traverse the left subtree, followed by the right subtree.
class TreeNode { constructor(value) { this.value = value; this.left = null; this.right = null; } } // Pre-order traversal function preOrderTraversal(node) { if (node !== null) { console.log(node.value); // Visit the current node preOrderTraversal(node.left); // Traverse left subtree preOrderTraversal(node.right); // Traverse right subtree } } // Usage example: 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('Pre-order traversal:'); preOrderTraversal(root); -
In-order Traversal:
- Traverse the left subtree, then visit the current node, followed by the right subtree.
// In-order traversal function inOrderTraversal(node) { if (node !== null) { inOrderTraversal(node.left); // Traverse left subtree console.log(node.value); // Visit the current node inOrderTraversal(node.right); // Traverse right subtree } } // Usage example (using the same tree as above): console.log('In-order traversal:'); inOrderTraversal(root); -
Post-order Traversal:
- Traverse the left subtree, then the right subtree, and finally visit the current node.
// Post-order traversal function postOrderTraversal(node) { if (node !== null) { postOrderTraversal(node.left); // Traverse left subtree postOrderTraversal(node.right); // Traverse right subtree console.log(node.value); // Visit the current node } } // Usage example (using the same tree as above): console.log('Post-order traversal:'); postOrderTraversal(root);
Breadth-First Traversal (Level-order Traversal):
- Visit nodes level by level, from left to right.
// Breadth-first (level-order) traversal using a queue
function breadthFirstTraversal(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
if (node !== null) {
console.log(node.value); // Visit the current node
if (node.left !== null) queue.push(node.left); // Enqueue left child
if (node.right !== null) queue.push(node.right); // Enqueue right child
}
}
}
// Usage example (using the same tree as above):
console.log('Breadth-first (Level-order) traversal:');
breadthFirstTraversal(root);
These traversal algorithms are fundamental for navigating tree structures in algorithms and data structures. They're essential in various computer science problems involving trees, such as binary trees, binary search trees, and more complex tree-like structures.
