Search in BST

by Alex Myronov

JavaScript

function Node(val) {
	this.val = val
	this.left = null
  this.right = null
}

const inorder = (root) => {
	if (!root) return null

  inorder(root.left)
  console.log(root.val)
  inorder(root.right)
}

const insert = (root, val) => {
	if (!root) {
  	return new Node(val)
  }
  if (root.val < val) {
  	root.right = insert(root.right, val)
  } else {
  	root.left = insert(root.left, val)
  }
  return root
}

const searchWithParent = (root, val, parent) => {
	if (!root) return null

  if (val === root.val) {
	  if (!parent) return null

		console.log(val > parent.val ? 'right' : 'left')
  	return parent
  }
  
  if (val > root.val) {
  	return searchWithParent(root.right, val, root)
  }
  
	return searchWithParent(root.left, val, root)
}

const search = (root, val) => {
	if (!root) return null

	if (root.right && val === root.right.val) {
  	console.log('right')
    return root
  } else if (root.left && val === root.left.val) {
	  console.log('left')
  	return root
  }

	return search(val > root.val ? root.right : root.left, val)
}

const searchIterative = (root, val) => {
	let parent = null
  let curr = root
  while (curr) {
  	if (val === curr.val) {
    	if (parent) {
      	console.log(parent.left.val === val ? 'left' : 'right')
      } else {
		      console.log('searching element is root', val)
      }  
      return parent
    }
    
    parent = curr
    curr = (val > curr.val) ? curr.right : curr.left
  }
  return null
}

const root = new Node(15)
insert(root, 10)
insert(root, 20)
insert(root, 8)
insert(root, 12)
insert(root, 16)
insert(root, 25)

//inorder(root)
console.log(searchIterative(root, 15))