I have this recursive generator method which yields the values of a BST in ascending order:

  *inOrder(node){

    if (node === null) {
      return;
    }

    if(node.left){
      yield * this.inOrder(node.left);
    }

    yield node.val;

    if(node.right){
      yield * this.inOrder(node.right);
    }

  }

The less sexy thing is you have to pass the root node in the method:

for(const v of bst.inOrder(bst.rootNode)){
     console.log(v);
 }

Worse is that a recursive generator is quite CPU intensive. I am trying to convert it to an iterator, to better understand what's going on, here is my attempt which is totally incomplete, using an iterative solution:

  [Symbol.iterator]() {

    // iterative solution?
    const queue = [this.rootNode];

    return {
      next(){

        return {
          done: true,
          value: // (last (right-most) value in tree)
        }

      }
    }

  }

I get the feeling an iterative solution to do depth-first search from left-to-right, will require a queue, but not sure. Alternatively, a recursive solution could work where we pass in the root node initially like so:

  [Symbol.iterator](node) {

    // recursive solution 
    return {
      next(){

        return {
          done: true,
          value: // (last (right-most) value in tree)
        }

      }
    }

  }

However, I am not sure how to implement with an iterator, either an iterative or recursive solution. So that's my question, how to take the generator code and use an iterator instead, somehow.

CodePudding user response：

Use a stack to store the nodes that need to be visited

Perform a dfs of the tree in a left-to-right order.

next method is called until all nodes in tree have been visited & iterator is done.

[Symbol.iterator]() {
  const stack = [];
  let currentNode = this.rootNode;

  return {
    next() {
      while (currentNode !== null || stack.length > 0) {
        if (currentNode !== null) {
          stack.push(currentNode);
          currentNode = currentNode.left;
        } else {
          const node = stack.pop();
          currentNode = node.right;
          return { done: false, value: node.val };
        }
      }
      return { done: true };
    }
  };
}

CodePudding user response：

With your data structure {left, val, right} you cannot avoid recursion (or a stack) if you want to traverse all nodes in inorder (left, then val, then right, what you call ascending order). And the *inOrder generator function does this perfectly. It can also be used to make the BST class an iterable:

class BST {
  constructor(root) {
    this[Symbol.iterator] = function() {
      return this.inOrder(root);
    }
  }
  * inOrder(node) {...}
}

Traversal without recursion is possible if you use a richer data structure, for example the "threaded representation" explained in Knuth, The Art Of Computer Programming taocp, section 2.3.1. In this representation, every node has a left link and a right link, and those that do not point to a child are called "threads", which point to the predecessor or successor node instead. Setting up these extra threads in the constructor (and updating them whenever a node is inserted or deleted) is extra work, but the iterator is then simplified to:

*[Symbol.iterator]() {
  var node = this.root;
  while (node.left && !node.leftThread) node = node.left;
  yield node.val;
  while (node) {
    var next = node.right;
    if (!node.rightThread)
      while (!next.leftThread) next = next.left;
    if (next) yield next.val;
    node = next;
  }
}

(This is just one example, there are doubtless many other data structures for trees.)

Whether the extra work with the extra data structure pays off depends on what happens more often to the tree: traversals or updates.