DEV Community

Arjun Rajkumar
Arjun Rajkumar

Posted on • Edited on

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

#challenge

Recent articles from Progress Updates:

Day 7: Question 2

Write a method to find the 2nd largest element in a binary search tree.

A binary search tree is a binary tree in which, for each node, the node's value is greater than all values in the left subtree, and the node's value is less than all values in the right subtree.

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

Top comments (1)

Collapse
 
arjunrajkumar profile image
Arjun Rajkumar •

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

Read next

adzhanfarhan profile image

Apa itu Damn Vulnerable Web Application (DVWA) ?

Adzhan Farhan Permada -

davidjonson profile image

How to Connect to an EC2 Windows Instance Using Remote Desktop 2024?

David Jonson -

ianbrumby profile image

Query your EventBridge Scheduled Events in DynamoDB

Ian -

shtefcs profile image

Transforming Business Today: 5 Key Ways AI and Automation Are Changing the Game

Stefan Smiljkovic -