Timing for all the chances [bridge hand]

[This is a hand from the 2000 Indian Nationals held in Baroda, and was given to me by Rajendra Gokhale.]

You are South and with no opposing bidding, you reach a small slam in hearts.

West leads the DK.

You see:

IMPS None	North ♠ A73 ♥ T73 ♦ 7643 ♣ Q64
	South ♠ KJ2 ♥ AKQJ4 ♦ J ♣ AKJT

West wins the trick and continues with the DQ.

How will you play?

[Please think about it before reading on.]



You have 2 spades, 5 hearts and 4 clubs. Where is the 12th trick going to come from?

If the hearts are 4-1, you probably have to rely on the spade finesse (a diamond-spade squeeze seems unlikely from the initial two tricks).

One option with hearts 3-2, is to ruff another diamond in hand and try for a diamond-spade squeeze/guess for finesse in the end position.

When hearts are 3-2 one could also think of trying for a dummy reversal: ruff 3 diamonds in hand, giving 6 heart tricks.

Opponents have been kind enough to lead the second round of diamonds, but you are still an entry short to dummy. You need the heart T to draw the last trump, and cannot use that as entry to ruff the diamonds in hand.

So, besides the heart T, SA and CQ, you need another entry.

Is there some situation where you can get an extra entry to do the dummy reversal?

The heart 7 should give you an idea: what if one opponent holds the heart 98 doubleton? Now you can use the heart Ten as an entry and use the H7 to draw the last trump!

With all these options available, you need to time your play correctly:

Ruff the second diamond with heart A. Play the heart K and the heart 4 to the T. Now you know whether heart 98 is doubleton or not, or whether the hearts are 4-1.

If hearts are 4-1, you just draw trumps, play clubs and rely on the spade finesse/unlikely diamond-spade squeeze.

If hearts are 3-2 with 98 doubleton, you can do a dummy reversal.

If hearts are 3-2 without the 98 doubleton, you can ruff a diamond and go for the squeeze/finesse ending.

The exact play to the tricks 2,3,4 is crucial: HA, HK, HT in that order. Deviate from that order, and you might not be able to pick the right play.

On the actual hand, the only chance that let it make was the dummy reversal with the heart 98 doubleton! The finesse and the squeeze don't work.

Solution to Construct the BST algo puzzle.

[This is a solution to the construct the binary search tree algorithm puzzle posted earlier]

A brief description of the puzzle:

If you insert $a_1$, then $a_2$, then $a_3$ and so on till $a_n$ into a binary search tree, with no rebalancing etc, you get a unique tree with $a_1$ as the root, $a_2$ as a child of the root etc.

A naive algorithm to construct the unique tree is $\Omega(n^2)$ in the worst-case.
(e.g: $a_1 \lt a_2 \lt \dots \lt a_n$).

Give an $O(n\log n)$ time algorithm to construct the tree.

We will present three solutions.

Solution 1)

---

This solution is based on Shyam's idea.

Initially we start with $(-\infty, \infty)$.

When we insert $a_1$ this interval splits into two: $(-\infty, a_1), (a_1, \infty)$. The left interval corresponds to the left sub-tree of $a_1$ and the right interval corresponds to the right sub-tree of $a_1$.

Basically, the binary search tree can be looked at as a collection of disjoint intervals, whose union is $(-\infty, \infty)$ (ignoring the split points).

Each time you insert a new value into a tree, some interval is split into two, around that value.

Now we can maintain the intervals as a red-black tree whose keys are the left end points, and the values are the right endpoints, plus a pointer to a node in the target tree (target tree is the tree which we want to construct). This node in the target tree holds the value which resulted in the creation of that interval.

Given a new value which we need to insert into the target tree, say $a_j$, we look-up the predecessor of $a_j$ in the tree of intervals ($O(\log n)$ time), and can now add the new node at the appropriate place in the target tree, in $O(1)$ time (and update the book-keeping).

Solution 2)

---

This solution is based on Arvind's idea, and is perhaps essentially the same as Solution 1). It is the simplest, though.

The key observation used in this solution is the following:

When you insert $x$ into a binary search tree, it will either be the right child of it's predecessor among the elements already present in the tree, or will be the left child of it's successor among the elements already present in the tree.

So you maintain a red-black tree along with the target tree. The nodes in the red-black tree maintain pointers to the corresponding node in the target tree, and also the when it was inserted (i.e. for $a_j$ you store $j$).

Now when you are inserting $a_j$, lookup both the successor and predecessor of $a_j$ in the red-black tree.

Say we get $a_p$ and $a_s$ with $a_p \lt a_j \lt a_s$.

Now if $p \lt s$ (predecessor was inserted before), then $a_j$ will be the left left child of $a_s$ in the target tree. If $p \gt s$, then $a_j$ will be the right child of $a_p$ in the target tree.

Solution 3)

---

This uses a lesser known data-structure called Cartesian Trees.

Given points $$(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$$ with $x_1 \lt x_2 \lt \dots \lt x_n$, a cartesian tree of these points is basically a treap (a tree + heap), with the $x_i$ forming the binary search tree values, and $y_i$ from the heap values: i.e. each node of the tree with contain an $(x_i, y_i)$ pair, and when you just look at the $x_i$, the tree will be a binary search tree, and when you just look at the $y_i$, the tree will be a heap.

This tree can be constructed in $O(n)$ time (see the wiki page for details).

Suppose the sorted list of $a_1, \dots, a_n$ is $b_1, \dots, b_n$, with $b_1 \lt b_2 \lt \dots \lt b_n$. Also, suppose $b_k = a_{f(k)}$.

Then we are looking for the Cartesian Tree corresponding to the points $$(b_1, f(1)), (b_2, f(2)), \dots, (b_n, f(n))$$ with the $f(i)$ forming a min-heap.

We can sort $a_i$ in $O(n \log n)$ time, and create the cartesian tree in $O(n)$ time.

AOSREMPHE

When I was at Microsoft, I was a part of a team which participated in puzzle hunts held by other Microsofties. The hunt ran over the weekend with people staying up all night solving puzzles!

Only a few teams managed to solve the final meta-puzzle, but it was quite satisfying to solve whatever amount we could solve.

The puzzles were very creative, with the winners of last year usually holding the contest for the current year.

This puzzle is a puzzle in that spirit.

The answer is one word.

[Solution]

Last 1000 digits puzzle

What are the last $1000$ digits of

$$1 + 50 + 50^2 + \dots + 50^{999}$$

when written in base-$10$?

i.e.

What are the last $1000$ digits of

$$ \sum_{k=0}^{999} 50^k$$

Of course, the idea is to find a way to find this manually/mathematically, and only use a calculator/computer if needed.

You don't have to list the $1000$ digits, just some simple, reasonably easy to compute (by a human) description would do too.

[Solution]

Solution to the two triangles puzzle.

[This is a solution to the two triangles geometry puzzle posted earlier]

The problem, repeated here:

In the figure below (not to scale, forgive the shoddy drawing skills).




$ABC$ is a triangle such that $\angle{BAC} = 60$ and $\angle{ABC} = 25$.

$DEF$ is an isosceles triangle, such that $\angle{EDF} = \angle{EFD}$, and $\angle{DEF} = 10$

(all angles are in degrees).

We also have that $|BC| = |DE|$ ($|XY|$ = length of the segment $XY$)

Show that $2|AC| + |DF| = |AB|$

Solution

---

Notice that $\angle{FDE} = 85$ and $\angle{ACB} = 95$, and so their sum is $180$.

Since $|BC| = |ED|$, we can position one copy of $\triangle{ABC}$ with $B$ coinciding with $E$ and $C$ coinciding with $D$ to get a bigger triangle.

Another copy of $\triangle{ABC}$, call it $\triangle{A'B'C'}$, can be positioned so that $B'$ coincides with $E$ and $C'$ coincides with $F$.

The result will be an even bigger triangle, $\triangle{EAA'}$ as below (more drawing incompetence):

Placing two copies of ABC along with DEF results in an equilateral triangle.

$\triangle{EAA'}$ is an equilateral triangle, and thus the base of the triangle which is $2|AC| + |DF|$ is same as the other side which is $|AB|$.

A Dream of Genie [bridge hand]

This hand has been stolen from the book Around the world in 80 hands by Zia Mahmood, which itself was stolen from Adventures in Card Play by Ottlik and Kelsey. This hand is so amazing, that I bought the 80 hand book because of this hand! (I already had the Adventures book at that time).

In the book, the chapter is titled "A Dream of Genie".

The story is about 3 bridge players who find a bottle with a genie who claims to be a master bridge player. With the genie making up the fourth, they had enough players to play a few hands of bridge.

This is the very first hand:

IMPS None	North ♠ 83 ♥ 963 ♦ AKQJ9 ♣ Q63
West ♠ KJ9652 ♥ - ♦ 87542 ♣ T8		Genie ♠ AQT4 ♥ A74 ♦ T63 ♣ KJ7
	South ♠ 7 ♥ KQJT852 ♦ - ♣ A9542

W	N	E	S
3S	P	4S	5H
all	pass

West leads the spade 2 against the contract of 5H by South, dummy plays the 3 and the genie sitting East, after some considerable thought, plays the 4!, South winning with the 7.

After this trick, the three players stuff the genie back into the bottle and throw him into the sea.

Later they show the hand to Micheal Rosenberg, expecting him to chuckle at the Genie's play, but Micheal Rosenberg calls them idiots and explains:

If East makes the normal plays of winning the spade and returning the suit (any other switch allows declarer access to diamonds), then South can ruff with the heart T, and lead the heart 8 to the dummy's 9. The Genie has to win this, but now any return he makes, declarer gets access to the dummy's winners. Even though East can ruff the 4th diamond, declarer can draw trump (if needed) and play the heart 2 to the heart 3!

If East ducks the first spade, as the Genie did, East avoids the throw-in, as he has a spade exit card when South plays the heart 8 to the heart 9.

Declarer must play the spade 8 at trick one to make it.
 

Constructing a Binary Search Tree [algorithm puzzle]

Suppose you are given a sequence of distinct numbers $a_1, a_2, \dots, a_n$.

You can create a unique binary search tree of those numbers by inserting $a_1$, then $a_2$ etc in the order they appear.

$a_1$ becomes the root, if $a_2 \gt a_1$, then it becomes the root of the right sub-tree and so on. Note that the sequence uniquely determines the tree.

For example, if the sequence was $4,5,1,2,3$ the corresponding binary search tree would look like

Tree formed by inserting 4, then 5,1,2,3 in order.

Now suppose you wanted to write a program to create the final binary search tree corresponding to a given insertion order.

A naive solution would be to run the binary search tree insertion algorithm for each element in the sequence to get the final tree. In the worst case, this creation algorithm would be quadratic in the number of elements in the sequence: if the sequence was sorted, for e.g.

This puzzle is about doing the binary search tree construction better.

Can you give an $O(n \log n)$ worst-case time algorithm which will construct the binary search tree of the given insertion sequence of distinct numbers $a_1, a_2, \dots, a_n$? Note that the resulting tree should be the same as the one gotten by the naive algorithm.

(Assume a pointer based tree, with left and right pointers, and if needed, parent pointers)

[Solutions]

Solution to Catch the Magical Monkey puzzle

[This is a solution to the catch the magical monkey puzzle posted earlier]

Brief description of the puzzle:

A monkey is moving at constant integer velocity among the integer points.

You can pick a point at any given time and check if the monkey is there. If he is there, you can catch him.

Can you eventually catch the monkey?

Solution

---

The solution relies on the following fact: $\mathbb{Z}^2$ is countable, and so there is a bijection mapping every ordered pair of integers $(a,b)$ to a natural number $f(a,b)$.

The strategy is to guess that the monkey's position at time $f(a,b)$ is $a + bf(a,b)$, corresponding to a guess of initial position $a$ and velocity $b$.

If the monkey's actual speed is $v$ and initial position was $u$, then we will catch him at time $f(u,v)$

A property of two triangles, geometry puzzle

[This is a geometry puzzle, solvable by elementary 8th grade geometry, i.e. no trigonometry etc]

In the figure below (not to scale, forgive the shoddy drawing skills).




$ABC$ is a triangle such that $\angle{BAC} = 60$ and $\angle{ABC} = 25$.

$DEF$ is an isosceles triangle, such that $\angle{EDF} = \angle{EFD}$, and $\angle{DEF} = 10$

(all angles are in degrees).

We also have that $|BC| = |DE|$ ($|XY|$ = length of the segment $XY$)

Show that $2|AC| + |DF| = |AB|$

[Solution]

Be careful at trick one (and two)

[Another hand I had posted to bridgebase forums]

You are South playing teams, and reach a contract of 5D.

West leads the spade 5.

You see:

IMPS None	North ♠ AQ3 ♥ Q752 ♦ 653 ♣ Q72
	South ♠ 642 ♥ AK ♦ AKQJ98 ♣ K3

You have 6 diamonds, 3 hearts, 1 spade and will definitely get a club after knocking out the CA. That is 11 tricks. So what is the problem?

The problem is that your only sure dummy entry is in spades and is in danger of getting knocked out before you can unblock your hearts.

You probably don't want to play the SA at trick one. If you play the Q, East might win the SK and continue spades. If East has both the SK and CA, you will not be able to get to dummy.

Consider what happens when you play low from dummy.

You have the S6 to cover West's card, so East has to win (otherwise you have 11 tricks without needing the HQ).

Now East cannot play spades without giving you a trick.

So play low and relax, right?

Not so fast.

Suppose East wins tricks 1, and returns a club. You have to go up with the K now.

If you play a low club from hand, West will win the CA, and play a spade, knocking out the SA while both hearts and clubs are blocked.

If you go up with the K, you will have the CQ as entry in case West wins. If the CK wins, you have the SA as entry. 

Catch the Magical Monkey puzzle

[This is another one of those puzzles that seem impossible at first]

You live in a one dimensional world, where the unit of time is seconds and everyone is immortal. At time = 0 seconds, a magical monkey appeared at some integer co-ordinate, and is known to be moving at a constant integer speed.

If it was at position x at time $t$ seconds, then it disappears, and then reappears at some position $x + v$ ($v$ could be negative) at time $t+1$ seconds, where it stays for a brief moment, then disappears and reappears at $x+2v$ at $t+2$ seconds and so on.

Both the initial point of appearance, and the speed of the monkey are not known to you, and you have no record of where the monkey has been so far.

You have access to magic too, and can appear at any point of your choosing. If you appear at a certain point the same time as the monkey, you can catch him.

In your world, time progresses linearly, and there is no time travel etc.

Can you catch the monkey in a finite amount of time (assume the current time is some $T \gt 0$)? (i.e. catch him eventually, and not be on a chase forever).

[Solution]

Solution to the "Is the Sum S?" Algorithm Puzzle

[This is a solution to the Is the sum S? algorithm puzzle posted earlier]

A description of the problem:

Given n numbers in the range [-M,M], and a target sum S, also in the range [-M, M], can you figure out in O(n) time, whether those n numbers add up to S, while keeping all your computations within the [-M, M] range? (M is unknown to you). Assume arithmetic operations are O(1).

Solution

---

Since the numbers are in the range [-M,M], the key observation we use is that adding a positive number to a negative number (or vice versa) will not overflow.

Thus we do the following:

Start with running sum = the negative of the target. Now we try to add the elements of the array to this running sum, hoping to see whether we get a zero in the end.

If the running sum is negative, add a positive number to it. If there are no positive numbers left in the array, then we know we cannot end with a total sum of 0.

If the running sum is positive, add a negative number to it. If there are no negative numbers left in the array, then we know we cannot end with a total sum of 0.

If the running sum is zero, add a positive or negative, does not matter.

Here is what a C++ implementation might look like (untested):

bool has_sum(const std::vector<int>& a, int target) {
  // Technically, the negation is a bug 
  // and overflow is possible here.
  // The range of int in C++ is actually 
  // [-M-1, M], not [-M, M].
  // But, we ignore that...
  int sum = -target;

  std::vector<int> positives;
  std::vector<int> negatives;
  int total = 0;

  // Collect the positive and negative numbers.
  for (auto x : a) {
    if (x > 0) {
      positives.push_back(x);
      total++;
    }
    if (x < 0) {
      negatives.push_back(x);
      total++;
    }
  }

  int positives_seen = 0;
  int negatives_seen = 0;

  // Note: no overflow in the + here :-)
  while (positives_seen + negatives_seen < total) {
    if (sum < 0) {
      // If sum is negative, try to add a positive.
      if (positives_seen >= positives.size()) {
        break;
      }
      sum += positives[positives_seen++];
    } else if (sum > 0) {
      // If sum is positive, try to add a negative.
      if (negatives_seen >= negatives.size()) {
        break;
      }
      sum += negatives[negatives_seen++];
    } else {
      // If sum is zero pick a positive.
      if (positives_seen < positives.size()) {
        sum += positives[positives_seen++];
      } else {
        // There is at least one negative left.
        sum += negatives[negatives_seen++];
      }
    }
  }

  return sum == 0;
} 

Try the duck

I had posted this hand on bridgebase forums a few years back, as a play problem for the intermediate players.

This was the hand:

IMPS None	North ♠ KQJ97 ♥ 93 ♦ 853 ♣ AQ4
	South ♠ 42 ♥ AQJ4 ♦ AKQ ♣ 6532

You are South, in a contract of 4NT in a team game (don't ask how you got there, this is a play problem). West leads the heart 2, you play the 9, and East plays the K which you win with the A.

[Please stop reading if you want to try and solve this first]

You have 3 hearts, 3 diamonds and 1 club. You can get 2 spades for sure and have a good chance of a third spade trick (remember, you are in 4NT).

Now if you play spade KQJ, then West with ATxx, can duck twice (or win second round). Now you are one entry short to cash the third spade and will need to rely on the club finesse.

Consider what happens when you play a spade to the 9 after winning the heart Ace. Even if it loses to the T, East cannot attack your dummy entry. This will allow you to lose two spade tricks while keeping the only entry in dummy to cash the third spade. If you play spades from the top, you might have to use up the dummy entry to setup the spades.

This only loses to the playing from the top only when East has a singleton T.

Playing to the K first and then to the 9 loses to Tx with East.

[Apologies to Charles Goren for swiping the title from his BOLS tip]

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.