Javascript - BST (Balanced and unbalanced trees) find In-Order Predecessor

Question

The function takes the root node of a binary tree and a target value and returns the node that comes before the target value in an in-order traversal.

Constraint is: If the target is the first value in an in-order traversal, return null.

function inOrderPredecessor(rootNode, target) {
  if (rootNode === null || rootNode.val === target) {
    return null
  }

  if (rootNode.left) {
    current = rootNode.left;
    while(current.right != null) {
      current = current.right;
    }
    return current.val;
  }

}

I've been working on this for hours and I keep hitting my head against a wall. An embarassingly long amount of time.. Over 4 hours watching videos etc.

The function can ONLY take in the rootNode and the target value.

Psuedo Code I have been thinking -

1. Start at left of rootNode since predecessor is always smaller.
2. From first left go right, until you can't go right anymore.
3. Return right most item when there are no more rights to take.

Answer 1

Use a recursive approach, that usually makes trees easier to handle:

function inOrderPredecessor(node, target) {
  if (node === null) {
    return null
  }
  if (target <= node.val) {
    // the node lies to the right of, or at the target value
    // so we need to find a node that precedes the target from the left child tree
    return inOrderPredecessor(node.left, target);
  } else { // target > node.val
    // the node lies to the left of the target value (and would qualify)
    // but there might be a node in its right child tree that is closer
    // (but not larger than or equal to the target)
    const res = inOrderPredecessor(node.right, target);
    if (res) {
      // if there is, return it
      return res;
    } else {
      // otherwise return the node itself
      return node;
    }
  }
}

It is also possible to write this with a loop that turns left and right, but not quite as straightforward:

function inOrderPredecessor(node, target) {
  var candidate = null;
  while (node) {
    if (node.val < target) {
      candidate = node;
      node = node.right;
    } else {
      node = node.left;
    }
  }
  return candidate;
}