## Solving puzzles at 30,000 feet [An iterative solution for the "Is this a binary search tree?" programming problem]

Sitting on a plane recently looking for a distraction, I recalled a programming challenge by James Michael Hare: Little Puzzlers-Is Tree a Binary Search Tree?. All I had to work with was a web browser, so I used JavaScript to come up with a solution. James subsequently blogged a recursive implementation in C# which is quite elegant. Wikipedia's Binary search tree page uses the same approach and C++ for its verification sample.

Because I did things a little differently, I thought I'd share - along with a few thoughts:

```
/**
* Determines if a tree of {value, left, right} nodes is a binary search tree.
* @param {Object} root Root of the tree to examine.
* @returns {Boolean} True iff root is a binary search tree.
*/
function isBinarySearchTree(root) {
var wrapper, node, stack = [{ node: root }];
while (wrapper = stack.pop()) {
if (node = wrapper.node) {
if ((node.value <= wrapper.min) || (wrapper.max <= node.value)) {
return false;
}
stack.push({ node: node.left, min: wrapper.min, max: node.value },
{ node: node.right, min: node.value, max: wrapper.max });
}
}
return true;
}
```

Notes:

- Tree nodes are assumed to have a numeric
`value`

and references to their`left`

and`right`

nodes (both possibly`null`

).- I used the name
`value`

(vs.`data`

) because it is slightly more specific.

- I used the name
- I decided on an iterative algorithm because it has two notable advantages over recursion:
- In the
*worst*case for a tree with`N`

nodes, an iterative solution has bookkeeping for`N/2`

nodes (when starting to process the leaf nodes of a balanced tree assuming nodes were queued) whereas a recursive solution has bookkeeping for all`N`

nodes (when processing the deepest node of a completely unbalanced tree).- Because there are two recursive calls, I don't
*think*tail recursion can be counted on to fix the worst-case behavior.

- Because there are two recursive calls, I don't
- The memory used for bookkeeping by an iterative solution comes from the heap which is generally
*much*larger than the thread stack. - To be fair, neither advantage is likely to be significant in practice - but they make good discussion points during an interview. :)

- In the
- The iterative algorithm has a disadvantage:
- Bookkeeping requires an additional object type (
`wrapper`

in the code above) which associates the relevant`min`

and`max`

bounds with pending`node`

instances.- ... unless you avoid the wrapper by augmenting the
`node`

elements themselves.- ... which is quite easy in JavaScript thanks to its dynamic type system.
- ... but still a violation of the separation of concerns principle.

- ... which is quite easy in JavaScript thanks to its dynamic type system.
- The creation/destruction of wrapper objects creates additional memory pressure.
- Although these objects are short-lived and therefore low-impact for typical garbage collection algorithms.

- ... unless you avoid the wrapper by augmenting the

- Bookkeeping requires an additional object type (
- I intended the code to be concise, so I made use of assignments in conditional expressions.
- This is not a practice everyone believes in (myself included!), but it seemed acceptable here.

- The code uses a stack (vs. a queue) because stacks tend to be simpler than queues - especially when implemented with an array.
- I made use of the fact that comparing a number to
`undefined`

evaluates to`false`

so I could avoid specifying explicit minimum/maximum values (as in the Wikipedia example) or making`HasValue`

checks (as in James's example). - If you have a different approach or a suggestion to simplify this one, please share!
- And note: I'm interested in algorithmic changes, not tweaks like removing extra parenthesis. :)