Tail Recursive Binary Tree Search Function JS

Question

I'm trying to write a tail recursive function contains(tree,element) that returns true if the element exists in the Binary tree, false otherwise.

I wrote the recursive function, the problem is that I don't know how to make it tail recursive

let leaf = { val: 6 }
let tree = {
  val: 10,
  sx: {
    val: 5,
    sx: {
      val: 13
    },
    dx: leaf
  },
  dx: {
    val: 32,
    sx: null,
    dx: null
  }
}

function contains(t,x) {

  if(t.val == x)
    return 1;

  let res = 0 ;
  if(t.sx)
    res += contains(t.sx,x)
  if(t.dx)
    res += contains(t.dx,x)

  return Boolean(res)
}

console.log(contains(tree,6))

why does this need to be tail-recursive? is this an assignment? — jdigital, Nov 27 '22 at 01:46
@ggorlen: Of course it does. [Most engines](http://kangax.github.io/compat-table/es6/#test-proper_tail_calls_%28tail_call_optimisation%29) however do not perform Tail Call Optimization. (Safari is the only major one that does, I believe; it used to be behind a flag on Webkit; I don't know if it still is.) — Scott Sauyet, Nov 28 '22 at 13:48
@ScottSauyet sure, you can code it in the language, but then since TCO isn't implemented in almost all engines it doesn't offer much concrete benefit, so it's unclear to me what OP hopes to achieve with the adjustment except for theoretical curiosity. — ggorlen, Nov 28 '22 at 15:21
For example, if OP's idea is that they want to process arbitrarily deep trees, they should use a stack and loop rather than attempt TCO. Canonical thread: [Are functions in JavaScript tail-call optimized?](https://stackoverflow.com/questions/37224520/are-functions-in-javascript-tail-call-optimized) — ggorlen, Nov 28 '22 at 15:28
@ggorlen: Yes, I don't know the OP's motivation either; I would guess it's a school assignment. The only real advantages I see to writing in a tail-recursive manner are that *(a)* if the JS vendors ever do get around to doing it, your code is ready to take advantage, and *(b)* with only minor modifications, you can then use trampolining to fix recursion depth issues. But these are real advantages, so I tend to do so when it doesn't overcomplicate an implementation. — Scott Sauyet, Nov 28 '22 at 15:42

score 2 · Accepted Answer · answered Nov 27 '22 at 01:45

I don't think this is possible to make completely tail recursive, because the number of recursive calls may be 1 or 2 (or 0) - in the case of 2, you can't have the final computation of the function be unconditionally returned, because you don't know whether a particular recursive call will be the final computation of the function.

That said, you can improve your code some. If the val matches, return true, and instead of adding to a res variable, return the first recursive call immediately if they're true. The second call can be made tail recursive because at that point, there's nothing left to check in the branch.

let leaf = {
  val: 6
}
let tree = {
  val: 10,
  sx: {
    val: 5,
    sx: {
      val: 13
    },
    dx: leaf
  },
  dx: {
    val: 32,
    sx: null,
    dx: null
  }
}

function contains(t, x) {
  if (t.val == x) {
    return true;
  }
  // Recursive, but not tail recursive:
  if (t.sx && contains(t.sx, x)) {
    return true;
  }
  // Tail recursive:
  return !t.dx ? false : contains(t.dx, x);
}

console.log(contains(tree, 6))

Would anything change if the binary tree was a binary search tree? — Grinza, Nov 27 '22 at 01:49
@GerardoFurtado Oh, you're right, thanks. With a BST, you can identify which branch node the value might possibly exist inside before recursing, by checking whether the value to find is less than or greater than the value of the current node. So, there would only have to be one recursive call - so it could be tail recursive. — CertainPerformance, Nov 27 '22 at 01:56
I think you can actually do it for an arbitrary binary tree. See my answer for details. — Scott Sauyet, Nov 28 '22 at 14:33

score 1 · Answer 2 · answered Nov 27 '22 at 02:19

For those interested, I leave the tail recursive version for binary search trees

let leaf = { val: 7}
let tree = {
  val: 10,
  sx: {
    val: 5,
    sx: {
      val: 4
    },
    dx: leaf
  },
  dx: {
    val: 32,
    sx: null,
    dx: null
  }
}

function _contains(t,x) {
  
  if(t.val == x)
    return 1;
  

  if(x < t.val && t.sx)
    return _contains(t.sx,x)
  else if(t.dx)
    return _contains(t.dx,x)    
}
function contains(t,x){
  
  return Boolean(_contains(t,x));
}

Scott Sauyet · Answer 3 · 2022-11-28T14:44:12.407

Although the discussion here has already come up with a tail-recursive solution for the binary search tree, it does seem to be possible to do a tail-recursive version for an arbitrary binary tree (or in fact for any tree.) The trick is that our core function will operate on an array of nodes, not on a single one.

Here we do a breadth-first traversal of the tree, stopping when we find the value or when we run out of nodes. Our recursive call is run on the tail of the input array plus the left and right children of the node. (Non-existent or null nodes are ignored.)

The public function simply wraps the input tree in an array and passes that to our main function.

const _contains = ([t, ...ts], x) =>
  t == undefined
    ? false
  : t .val == x
    ? true
  : _contains (ts .concat (t .sx || []) .concat (t .dx || []), x)

const contains = (t, x) => 
  _contains ([t], x)


let tree = {val: 10, sx: {val: 5, sx: {val: 13}, dx: {val: 6}}, dx: {val: 32, sx: null, dx: null}};

[10, 12, 13, 32, 42] .forEach (x => console .log (`${x} --> ${contains (tree, x)}`))

I'm loathe to do it, on general principles, but this would definitely be made significantly more efficient if we pushed children onto the array and recurred on an index instead, with something like this:

const push = (x) => (xs) => 
  x ? ((xs .push (x)), xs) : xs

const _contains = (ts, i, x) =>
  i >= ts .length
    ? false
  : ts [i] .val == x
    ? true
  : _contains (push (ts [i] .dx) (push (ts [i] .sx) (ts)), i + 1, x)

const contains = (t, x) =>
  _contains ([t], 0, x)

But the main point is simply that by using an array of nodes, we can prepare for that TCO that never seems to come, unless you're a Safari user.

Tail Recursive Binary Tree Search Function JS

3 Answers3