A depth-first tree iterator

The iterator pattern is nice because it gives the caller a simple flat-looking looping mechanism to traverse data entries. Consider the following pseudocode for traversing a tree depth-first.

const tree = {
  id: 1,
  left: {
    id: 2,
    left: { id: 3, left: null, right: null }
    right: null,
  },
  right: {
    id: 4,
    left: {
      id: 5,
      left: null,
      right: { id: 6, left: null, right: null },
    },
    right: {
      id: 7,
      left: null,
      right: { id: 8, left: null, right: null },
    }
  }
};

traverse(tree, onEmit);

function onEmit(node) {
  console.log(node.id);
}

function traverse(node, onEmit) {
  if (node == null) return;
  
  onEmit(node);
  
  if (node.left) traverse(node.left, onEmit);
  if (node.right) traverse(node.right, onEmit);
}

The program above takes a recursive approach to traversing a tree structure. While this may not be ideal in situations with very large tree structures, the program would print the following output when run:

1
2
3
4
5
6
7
8

Consider instead a breadth-first approach to traversing a tree:

function traverse(node, onEmit) {
  if (node == null) return;
  
  emit(node, onEmit);
  descend(node, onEmit);
}

function emit(node, onEmit) {
  if (node) onEmit(node);
  if (node.left) onEmit(node.left);
  if (node.right) onEmit(node.right);
}

function descend(node, onEmit) {
  traverse(node.left, onEmit);
  traverse(node.right, onEmit);
}

Note that I actually think the logic above is wrong.

---

Let's take the depth-first example and turn it into an iterator.

An iterator is an object with a next method that will return the following node in the tree. Once there are no more nodes, the next method will return null.

Let's look at the depth-first example again.

function onEmit(node) {
  console.log(node.id);
}

function traverse(node, onEmit) {
  if (node == null) return;
  
  onEmit(node);
  
  if (node.left) traverse(node.left, onEmit);
  if (node.right) traverse(node.right, onEmit);
}

Let's try to first model the recursion in an iterative manner.

function traverse(node, onEmit) {
  if (node == null) return;
  
  onEmit(node);
  
  // This should be represented by some data structure
  if (node.left) traverse(node.left, onEmit);
  // This should be represented by some data structure
  if (node.right) traverse(node.right, onEmit);
}

Let's think of the steps that are executed and see how we can decompose this recursive function into an iterative one.

Here's our example tree again:

const tree = {
  id: 1,
  left: {
    id: 2,
    left: { id: 3, left: null, right: null }
    right: null,
  },
  right: {
    id: 4,
    left: {
      id: 5,
      left: null,
      right: { id: 6, left: null, right: null },
    },
    right: {
      id: 7,
      left: null,
      right: { id: 8, left: null, right: null },
    }
  }
};

• Call traverse(tree, onEmit)
• node = tree
• Check if node is null - it's not, so continue
• emit node (1)
• Check if node.left is null - it's not, so let's traverse
• prev = node
• node = node.left
• check if node.left is null - it's not, so let's traverse **

** At this point, we realize that we're checking if node.left and node.right are null before we traverse. Then, we check again at the start of traverse. Let's just do it at the start of traverse only.

function traverse(node, onEmit) {
  if (node == null) return;
  
  onEmit(node);
  
  traverse(node.left, onEmit);
  traverse(node.right, onEmit);
}

Let's start again.

• Call traverse(tree, onEmit)
• node = tree(1)
• Check if node is null - it's not, so continue
• emit node (1)
• Check if node(1).left is null - it's not, so let's traverse
• prev = node(1)
• node = node(1).left(2)
• Check if node is null - it's not, so continue
• emit node (2)
• prev2 = node(2)
• node = node(2).left(3)
• Check if node is null - it's not, so continue
• emit node (3)
• prev3 = node(3)
• node = node(3).left(null)
• Check if node is null - It is, so skip this
• node = prev3(3)
• node = node(3).right(null)
• Check if node is null - It is, so skip this
• node = prev3(3)
• We've checked both prev3 left and right, so go back higher
• prev3 = empty
• node = prev2(2)
• node = node(2).right(null)
• Check if node is null - it is, so skip this
• node = prev2(2)
• We've checked both prev2 left and right, so go back
• prev2 = empty
• node = prev(1)
• node = node(1).right(4)

---

I think we need to come up with a max