Iteration_Protocol_JS
Iteration Protocol in JS
Symbol.Iterator
In JavaScript, the Symbol.iterator
is a special symbol that defines the default iterator for an object. When you use for...of
, spread syntax (...
), or destructuring on an object, JavaScript looks for this iterator.
A generator function (function*
) simplifies creating iterators because it automatically handles the iterator protocol. The yield
keyword in a generator pauses execution and returns a value when the iterator’s next()
method is called.
Example: Simple Iterable Object
const iterableObject = {
*[Symbol.iterator]() {
yield 1;
yield 2;
yield 3;
}
};
for (const value of iterableObject) {
console.log(value);
}
// Output: 1, 2, 3
Binary Tree Class
Before we dive into DFS and BFS, let’s define a basic binary tree structure:
class TreeNode {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
class BinaryTree {
constructor(root = null) {
this.root = root;
}
}
This defines:
TreeNode
to represent each node in the binary tree.BinaryTree
to hold the root node and traversal logic.
Depth-First Search (DFS) with Symbol.iterator
Depth-First Search (DFS) explores as far as possible along each branch before backtracking. Common DFS traversals include in-order, pre-order, and post-order.
In-Order Traversal (Left, Root, Right)
Here’s how you can implement in-order traversal using yield
:
class BinaryTree {
constructor(root = null) {
this.root = root;
}
*inOrderTraversal(node) {
if (node) {
// Traverse left subtree
yield* this.inOrderTraversal(node.left);
// Yield current node's value
yield node.value;
// Traverse right subtree
yield* this.inOrderTraversal(node.right);
}
}
[Symbol.iterator]() {
return this.inOrderTraversal(this.root);
}
}
Application
const tree = new BinaryTree(
new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3)
)
);
for (const value of tree) {
console.log(value);
}
// Output: 4, 2, 5, 1, 3
This approach works for other DFS traversals like pre-order or post-order by changing the order of recursive calls and the yield
statements.
Breadth-First Search (BFS) with Symbol.iterator
Breadth-First Search (BFS), also known as level-order traversal, visits nodes level by level from top to bottom.
Here’s how you can implement BFS using a queue:
class BinaryTree {
constructor(root = null) {
this.root = root;
}
*breadthFirstTraversal() {
if (!this.root) return;
const queue = [this.root];
while (queue.length > 0) {
const current = queue.shift();
yield current.value;
if (current.left) queue.push(current.left);
if (current.right) queue.push(current.right);
}
}
[Symbol.iterator]() {
return this.breadthFirstTraversal();
}
}
Usage
const tree = new BinaryTree(
new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, null, new TreeNode(6))
)
);
for (const value of tree) {
console.log(value);
}
// Output: 1, 2, 3, 4, 5, 6
Full Example: Combining DFS and BFS
class BinaryTree {
constructor(root = null) {
this.root = root;
}
*inOrderTraversal(node) {
if (node) {
yield* this.inOrderTraversal(node.left);
yield node.value;
yield* this.inOrderTraversal(node.right);
}
}
*breadthFirstTraversal() {
if (!this.root) return;
const queue = [this.root];
while (queue.length > 0) {
const current = queue.shift();
yield current.value;
if (current.left) queue.push(current.left);
if (current.right) queue.push(current.right);
}
}
[Symbol.iterator]() {
return this.inOrderTraversal(this.root); // Change to breadthFirstTraversal for BFS
}
}
// Example usage
const tree = new BinaryTree(
new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, null, new TreeNode(6))
)
);
console.log('DFS:');
for (const value of tree) {
console.log(value);
}
console.log('BFS:');
tree[Symbol.iterator] = tree.breadthFirstTraversal.bind(tree);
for (const value of tree) {
console.log(value);
}