DEV Community

loading...

Discussion on: Write better code: Day 7 - Second largest item in Binary search tree

Collapse
arjunrajkumar profile image
Arjun Rajkumar Author

Logic

  • The right most item will be the largest.
  • The second largest could be one of these:
  • If the current node has only one left-subtree, then the second largest could be the right most child of that sub-tree
  • Else, second largest is parent
def largest(root)
  if root.any? && root.right
    return largest(root.right) 
  end

  return root.value
end

def second_largest(root)
  return largest(root.left) if root.any? && (root.left && !root.right)

  return root.value if root.any? && (!root.left && !root.right)

  #if both of them are false then go right
  return second_largest(root.right)
end