Tail Recursive Binary Tree Search Function JS-CodePudding

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))

CodePudding user response：

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))