Implement tree traversal iterator javascript

Hard

Implementing a JavaScript Tree Iterator with Multiple Traversal Strategies using Generators

Implement a tree traversal iterator that supports different traversal strategies. What's the correct implementation?

Choose an option below

[Symbol.iterator]() {
  const values = [];
  const traverse = (node) => {
    if (!node) return;
    traverse(node.left);
    values.push(node.value);
    traverse(node.right);
  };
  traverse(this.root);
  return values[Symbol.iterator]();
}

*[Symbol.iterator]() {
  const stack = [];
  let current = this.root;

  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    
    current = stack.pop();
    yield current.value;
    current = current.right;
  }
}

[Symbol.iterator]() {
  return {
    stack: [],
    current: this.root,
    next() {
      while (this.current) {
        this.stack.push(this.current);
        this.current = this.current.left;
      }
      
      if (this.stack.length === 0) {
        return { done: true };
      }
      
      const node = this.stack.pop();
      this.current = node.right;
      return { value: node.value, done: false };
    }
  };
}

[Symbol.iterator]() {
  const values = [];
  const stack = [this.root];
  
  while (stack.length) {
    const node = stack.pop();
    if (node) {
      values.push(node.value);
      stack.push(node.right, node.left);
    }
  }
  
  return values[Symbol.iterator]();
}

JavascriptIteratorsGeneratorsTree traversalData structures

1class TreeNode {
2  constructor(value) {
3    this.value = value;
4    this.left = null;
5    this.right = null;
6  }
7}
8
9class TreeIterator {
10  constructor(root, strategy = 'inorder') {
11    this.root = root;
12    this.strategy = strategy;
13  }
14
15  // Missing implementation
16  [Symbol.iterator]() {
17    ____________________
18    ____________________
19    ____________________
20    ____________________
21  }
22}
23
24// Usage:
25const tree = new TreeNode(1);
26tree.left = new TreeNode(2);
27tree.right = new TreeNode(3);
28tree.left.left = new TreeNode(4);
29tree.left.right = new TreeNode(5);
30
31for (const value of new TreeIterator(tree, 'inorder')) {
32  console.log(value); // Should output: 4, 2, 5, 1, 3
33}

Implementing a JavaScript Tree Iterator with Multiple Traversal Strategies using Generators

Hint

Related Questions