Second Largest in BST

Find second largest element in BST

by Alex Myronov

JavaScript

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

Node.prototype.insertLeft = function(value) {
	this.left = new Node(value)
  return this.left
}
Node.prototype.insertRight = function(value) {
	this.right = new Node(value)
  return this.right
}

const tree = new Node(5)
tree.insertLeft(3)
const right = tree.insertRight(12)
const rightLeft = right.insertLeft(9)
rightLeft.insertRight(11)

const findLargest = (node) => {
	let curr = node
  while (curr) {
  	if (!curr.right) {
    	return curr
    }
    curr = curr.right
  }
  return curr
}

const findSecondLargest = (node) => {
	if(!node) {
  	return null
  }
  
  let parent = null
  let curr = node
  
  while (curr) {
  	if(!curr.left && !curr.right) {
    	return parent
    }
    
    if(curr.left && !curr.right) {
    	return findLargest(curr.left)
    }
    
    parent = curr
    curr = curr.right
  }
  return parent
}

console.log(findSecondLargest(tree))