# The blog of dlaa.me

## 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 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.
• 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. :)
• 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.
• 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.
• I intended the code to be concise, so I made use of assignments in conditional expressions.
• 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. :)