Iterators part three: A General Binary Tree Iterator

[This is part three in a series about iterators]

Introduction

---

If you have heard of binary trees, you probably know what in-order, pre-order and post-order traversals are. These traversals are usually defined in a recursive fashion.

For instance, in-order is defined: traverse left sub-tree, visit node, traverse right sub-tree.

These kind of definitions lead to easy recursive implementations.

A common interview question is to convert these recursive method to iterative methods, which can be solved in a general fashion by doing what the compilers do: simulate the recursion using a call stack.

A possible followup to that is to add the ability to do the traversal in a lazy fashion: provide a next interface, which will return the visited nodes one by one (with next being reasonably efficient). [One could use yield, if the language provides it, but we will assume that it is unavailable.]

If you search the web, you will probably see different iteration solutions, custom made for in-order, pre-order etc.

A General Lazy Iterator for Binary Trees

---

In this article we will discuss a general lazy iterator for binary trees, for traversals defined recursively. This includes not just in-order etc, but also crazy traversals like traverse left node, traverse right node, visit node, visit node, traverse left node.

These general traversals can be represented as a string consisting of the letters "L", "R" and "V".

For instance, in-order traversal is "LVR", L for traverse left sub-tree, V for visit node and R for traverse right sub-tree. Post-order is "LRV" and the crazy traversal defined above is "LRVVL".

So, given a traversal method in the form a traversal string (like "LVR" and which contains at least one V), and the tree, we would like to create a lazy iterator, which will allow us to visit the nodes of the given tree in the given traversal order.

If you were to write a recursive method for the traversal, the code might look something like this (python):

# traversal_method is a string like "LVLR".
def traverse(tree, traversal_method):
    if tree == None:
        return
    for method in traversal_method:
        if method == "L":
            traverse(tree.Left, traversal_method)
        if method == "R":
            traverse(tree.Right, traversal_method)
        if method == "V":
            Visit(tree.Value) 

This recursive method can be converted to an iterative method, by maintaining a stack of (tree,  traversals_left) pairs.

For example, if the traversal required is "LVR", we first push the (root, "LVR") pair. Once the left sub-tree is traversed because of the "L" (started by pushing the left child), we update that to (root, "VR"), we then visit the node, update that node to (root, "R"), then traverse the right sub-tree.

Once a node's traversals_left becomes empty, we pop it off the stack, pick up what is on the top, examine what needs to be done and continue.

This is what the iterative version might look like (python):

# traversal_method is a string like "LVLR".
def traverse(tree, traversal_method):
    if tree == None:
        return
    stack = [(tree, traversal_method)]
    while len(stack) > 0:
        node, traversal_left = stack[-1]
        del stack[-1] # pop
        if node == None:
            continue
        # in python L[-1] is the last element of the list.
        # and L[1:] is the list without the first element.
        if len(traversal_left[1:]) != 0
            # push.
            stack.append((node, traversal_left[1:]))
        if traversal_left[0] == "L":
            stack.append(node.Left, traversal_method)
        if traversal_left[0] == "R":
            stack.append(node.Right, traversal_method)
        if traversal_left[0] == "V":
            visit(node.Value)        

In languages that support yield, an easy way to make this lazy would be to replace visit(node.Value) above with yield node.Value.

Assuming we don't have such a language feature, we want to implement a next interface, which can give us the nodes one at a time, and in a reasonably efficient manner (both worst case and amortized per call).

[We could probably blindly simulate what the C# compiler/python interpreter does behind the scenes for implementing yield, but the result might turn out to be an unreadable mess and we will probably have to spend some effort making it readable, anyway.]

We implement next as two steps.

First step is move, which will do the iteration of pushing/popping nodes into/off the stack, till we get to a node which needs to be visited, resulting in the appropriate node being at the top of the stack.

The second step of next would be to update the top of the stack indicating that a visit was just performed (and returning the tree node to the caller).

We also maintain the invariant that only the move step will change the size of the stack.

A C++ implementation might look like: [Click here to expand/collapse]

#include "tree.h" // Tree definition.
#include <stack>

using std::stack;

struct TraverserHelper {
  Tree *node;
  size_t action;
};

typedef struct TraverserHelper THData;

// A class which provides lazy iteration of
// arbitrary traversals of a binary tree. 
// Traversal specified as 
// "LVR" (left, visit, right, for in-order)
// or 
// "LRV" for post-order
// or 
// something strange like "LVLVR".
// Provides a next() interface, 
// which returns a pointer to a Tree node.
// Returns NULL when nothing more to traverse.
// TODO: implement operator++ etc.
// Note: prototype implementation. You might find
// this ugly etc.
class Traverser {
public:
  Traverser(Tree *root, const char * traversal_method) {
    _method = traversal_method;
    _len = strlen(traversal_method);
    THData d;
    d.node = root;
    d.action = 0;
    _stack.push(d);
  }

  Tree *next() {
    move();
    if (_stack.empty()) {
      return NULL;
    }
    THData top = _stack.top();
    _stack.pop();
    Tree *ret = top.node;
    top.action++;
    _stack.push(top);
    return ret;
  }

private:
  void move() {
    while (!_stack.empty()) {
      THData top = _stack.top();
      _stack.pop();
      // Needs popping.
      if (top.node == NULL || top.action == _len) {
        continue;
      }
      Tree *cur = top.node;
      Tree *next = NULL;
      bool yield = false;
      switch(_method[top.action]) {
        case 'V':
          yield = true;
          break;
        case 'R':
          if (cur->Right != NULL) {
            next = cur->Right;
          }
          break;
        case 'L':
          if (cur->Left != NULL) {
            next = cur->Left;
          }
      }
      if (yield) {
        // Don't increment action here, as
        // the node hasn't been visited yet.
        _stack.push(top);
        break;
      }
      top.action++;
      if (top.action < _len) {
        _stack.push(top);
      }
      if (next) {
        THData nData;
        nData.node = next;
        nData.action = 0;
        _stack.push(nData);
      }
    }
  }

  std::stack <THData> _stack;
  const char * _method;
  size_t _len;
};
 

And here is a sample usage of this iterator

// Determine if two nodes of a binary search tree
// sum to target.
bool has_sum(Tree *tree, int target) {
  if (tree == NULL) return false;

  Traverser ascending(tree, "LVR");
  Traverser descending(tree, "RVL");

  Tree *left = ascending.next();
  Tree *right = descending.next();

  while (left->Value <= right->Value;) {
    int sum = left->Value + right->Value;
    if (sum == target) {
      return true;
    }
    if (sum > target) {
      right = descending.next();
    } else {
      left = ascending.next();
    }
  }
  return false;
} 

Analysis of next

---

If the size of the traversal description string is T [O(1) for most useful cases], and the maximum depth of tree is H, then next would run in O(TH) time, and would use O(TH) space.

Even though each call to next is O(TH), it is O(T) amortized per node visited (averaging over the whole traversal), as each node and each edge of the tree is touched only O(T) times.

Conclusion

---

Even though any recursive implementation which returns a list of elements, can theoretically be modified into a lazy iterative version, explicitly doing it for a binary tree was an interesting exercise.

This approach can also be generalized to general trees, where instead of "L" and "R", we can use child numbers etc.

Iterators part two: Using the Odometer

[This is part two in a series about iterators.]

Introduction

---

Like the odometer of a car, the odometer we consider is basically a counter, with one generalization: each position could cycle through a different number of "digits" (each position starts at digit 0).

[Digits in quotes, because we could have one position go from, say, 0 to 999, each number is considered a digit, in base 1000.]

The general odometer works just like the one in the car.

Every time you need to increment the odometer, you increment the digit in the rightmost position (going back to 0 if you are at the largest possible digit for that position). If the increment results in that position cycling back to 0, you increment the position to the left of it. If that results in cycling back of that position to 0, you move one position left and so on.

Basically, simulating hand addition with carries.

When all the digits reach the maximum value, we cannot increment anymore. An odometer can easily be implemented as an iterator, to provide a has_next, next interface with next incrementing the counter by one.

Here is how an implementation might look like (C++):

#include <vector>

// Represents a generalized odometer.
class Odometer {
public:
  // 0 is the right most position.
  Odometer(const std::vector<int>& max_digits) {
    _max_digits = max_digits;
    for (int i = 0; i < max_digits.size(); i++) {
      _odometer.push_back(0);
    }
    _overflow = false;
  }

  bool has_next() const {
    for (int i = 0; i < _odometer.size(); i++) {
      if (_odometer[i] != 0 ) {
        return true;
      }
    }
    // All zeroes. If we overflowed,
    // we are at the end.
    return false || !_overflow;
  }

  // returns the current, but increments before
  // returning.
  std::vector<int> next() {
    _overflow = true;
    std::vector<int> current = _odometer;
    for (int i = 0; i < _odometer.size(); i++) {
      _odometer[i] = (_odometer[i] + 1) % _max_digits[i];
      if (_odometer[i] != 0) {
        break;
      }
    }
    return current;
  }

private:
  bool _overflow;
  std::vector<int> _odometer;
  std::vector<int> _max_digits;
}; 

We will now discuss how we can do a iterator based generation of permutations using an odometer (and briefly, Cartesian products and power-set enumeration).

Generating Permutations

---

[If you want to try solving the problem of implementing a has_next, next type of iterator for permutations using an odometer, please stop reading]

While the method discussed below is not optimal (unlike Heap's method, [in fact, not even asymptotically optimal]), and generates permutations in a "weird" order (unlike Narayana Pandita's method of generating in lexicographic order), it is an interesting application of odometers.

Say we want to provide an iterator to generate all the permutations of $1,2, \dots, n$, with a has_next, next interface.

The idea is to use a suitable odometer as a black-box, and map each odometer state to a permutation uniquely.

Since there are $n!$ permutations, an odometer that suggests itself:

The odometer has $n-1$ digits, $d_1, d_2, \dots, d_{n-1}$ with $d_1$ being the left-most.

The maximum possible digit achievable by $d_1$ is $n-1$, and so total $n$ digits for $d_1$, which are $\{0,1,2, \dots, n-1\}$.

Maximum digit for $d_2$ is $n-2$ and so on (max for $d_i$ being $n-i$).

This odometer can count upto $n\times(n-1)\times\dots\times 1 = n!$, exactly the number of permutations.

To generate a permutation given the odometer $[d_1, d_2, \dots, d_{n-1}]$, we can use the following method.

Start with $n$ empty circles in a row.

Write $1$ in the $(d_1+1)^{th}$ circle from the left.

Write $2$ in the $(d_2+1)^{th}$ empty circle from the left.

Write $3$ in the $(d_3+1)^{th}$ empty circle from the left.

and so on.

Once you have written $n-1$, there will be one empty circle left, where you write $n$, resulting in a permutation of $1,2,\dots, n$.

Notice that in the resulting permutation, the number of numbers greater than $i$, which appear to the left of $i$ is precisely $d_i$. In other words $[d_1, d_2, \dots, d_{n-1}]$ is the inversion table of the permutation, which tells you how many inversions a given number has.

It is not difficult to see that each odometer state generates a unique permutation.

If the odometer can be implemented as an iterator with has_next, next, so can the permutation generator.

There is an easy $O(n^2)$ time algorithm to map the odometer state to the permutation. Even $O(n\log n)$ is achievable.

Generating Cartesian Products

---

The Cartesian product of sets $A_1, A_2, \dots, A_n$ is the set of tuples $(a_1, a_2, \dots, a_n)$ such that $a_i \in A_i$.

If the size of $A_i$ is $s_i$, then the number of such tuples is $s_1\times s_2\times \dots \times s_n$.

An odometer for this is $[d_1, d_2, \dots, d_n]$ where $d_i$ cycles through $s_i$ digits. Given an odometer state $[d_1, d_2, \dots, d_n]$, we pick the $(d_i+1)^{th}$ element from $A_i$ for the corresponding element of the resulting tuple.

The mapping can be done in $O(n)$ time, assuming the $k^{th}$ element of $A_i$ can be picked in $O(1)$ time.

Generating Subsets

---

If we want to generate all the subsets of $\{a_1, a_2, \dots, a_n\}$, we can represent each set as a bit-vector $[v_1, v_2, \dots, v_n]$, where $v_i = 1$ iff $a_i$ is in the set.

We can use the odometer $[d_1, d_2, \dots, d_n]$ with each $d_i$ cycling through exactly two digits.

We pick $v_i = d_i$.

This mapping can be done in $O(n)$ time.

Conclusion

---

The generalized odometer seems to be a useful tool for use in implementing has_next, next type of iterators for certain combinatorial objects.

Also, given a number $M$ we can directly construct (and vice-versa) the odometer corresponding to $M$ increments, without having to increment $M$ times.

This direct mapping allows us to compute the $M^{th}$ permutation, Cartesian product, or subset directly (without having to perform $M$ increments). This would be useful to parallelize the generation and processing of those objects.

Iterators part one: Lazy shuffling with the Knuth Shuffle

[This is part one in a series about iterators.]

tl;dr: Generate a random permutation of $1,2 \dots, n$ lazily. Skip to the section titled Lazy Shuffle if you already know how the Knuth Shuffle works.

Introduction

---

Suppose you are working on something where you needed to create a random permutation of $1,2,\dots, n$ and process the random permutation one element at a time, potentially stopping the processing long before you run out of the n elements. How many elements you need to process is dependent on the elements you see (i.e. you don't know it before hand).

For example, n could be a billion, and you process the first 1000 elements in some cases, 100 in some etc.

A well known way to create a random permutation/shuffle is the Knuth Shuffle. In the Knuth shuffle, you are given an array, and the algorithm creates a random, in-place permutation of the array, in $O(n)$ time.

The idea of the Knuth shuffle is actually quite simple.

An explanation of Knuth Shuffle

---

The array consists of two portions, the shuffled portion and the yet to be shuffled portion. Initially the whole array is yet to be shuffled.

The shuffled portion will grow from the right to the left (i.e. initially empty, then $(A[n-1])$, then $(A[n-1], A[n-2])$ etc). You now pick a random object from the yet to be shuffled portion and move it to the location which will grow the shuffled portion by one. This will result in the displacement of a yet to be shuffled object. That object you move to the empty space created by the newly selected object that was just moved to the shuffled portion.

Lazy Shuffle

---

We could apply the Knuth shuffle to our problem, by creating an array $A$ of size n, such that $A[i] = i$, performing the Knuth shuffle on it, and process the elements in the order $A[0], A[1], \dots$.

Since n could be a billion, the time and space costs of this could be wasteful.

A practical approach would be to repeatedly generate a random number from $1$ to $n$ and check if you have generated that number before. If you have seen it before, you regenerate. This is a big improvement, but still wasteful, with the potential to run for a long time.

We can actually make the Knuth Shuffle work for us in a lazy fashion, without having to pay the $O(n)$ space or time costs.

Assuming we need to process only $m$ elements ($m$ unknown to us), there is a way to make only $m$ random number calls, and use $O(m)$ space, and run in $O(m)$ expected time.

We can achieve this by simulating the array in the Knuth shuffle by a hashtable.

[We can also use a sparse array implementation of the array, which will use $\Theta(n)$ space, but the running time will still be $O(m)$]

If we are simulating the array $A$, then the key will be $i$, and the value will be $A[i]$. The hashtable will only contain entries for elements that have been touched (read or written to). The first time we try to read $A[i]$, the hashtable will create an entry for it, setting the value to be $i$.

This allows us to provide the hasNext, next style iterator for the shuffled elements.

Here is what the code might look like (C++).

#include <map>  // For unordered_map
#include <random>  // Assume exists with some API.

// Sample usage:
// LazyShuffle ls(1000000);
// while (ls.has_next()) {
//     int v = ls.next();
//     Status s = process(v);
//     if (s.Done()) break;
// }
class LazyShuffle {
public:
    // generates a random permutation of 0 to n-1.
    LazyShuffle(int n)
        : _to_shuffle(n) {
    };

    bool has_next() {
        return _to_shuffle > 0;
    }

    int next() {
        // Do the Knuth shuffle here.
        // [yet to be shuffled] [shuffled]

        // Generate a random number from
        // 0 to _to_shuffle-1;
        _to_shuffle--;
        int selected = _random.generate(0, _to_shuffle);

        // Now swap this with element which 
        // grows the shuffled part
        swap(selected, _to_shuffle);

        return get(_to_shuffle);
    }

private:
    void set(int idx, int value) {
        _array[idx] = value;
    }

    int get(int idx) {
        if (_array.find(idx) == _array.end()) {
            _array[idx] = idx;
        }
        return _array[idx];
    } 

    void swap(int idx1, int idx2) {
        int val1 = get(idx1);
        int val2 = get(idx2);
        set(idx1, val2);
        set(idx2, val1);
    }

    // We use unordered_map, but we can use a hashtable
    // with expected O(1) time operations.
    std::unordered_map<int, int> _array; 

    // The number of elements not shuffled.
    int _to_shuffle;

    // Assume exists
    random::Generator _random;
};