Given a BST find the second largest element?

Question

Sigiloso · Accepted Answer

Since A binary search tree is arranged into subtrees  such that, the left subtree contains the values which are less than the root node and the right subtree contains the values which are larger than the root node.

So, the largest element will be the Rightmost element of the right subtree.

And the SECOND largest element will be it's parent.

int findSecondLargest(tree *root)
{
  tree *ptr, *prevPtr;
  prevPtr = NULL;
  ptr = root;

  while( ptr->right != NULL)
  {
    prevPtr = ptr;
    ptr = prevPtr->right;
   }

  if (ptr->left == NULL)
     return (prevPtr->info) ;          // if ptr is the rightmost leaf node, then return its parent node

// else if it has a left subtree then return the rightmost node in the left subtree.

  prevPtr = ptr;
  ptr = ptr->left;

  while (ptr ! = NULL)
  {
     prevPtr = ptr;
     ptr = ptr ->right ;
  }
 return (prevPtr->info) ;
}

mindpower · Answer

Node findSceondLargest(Node root) {
  // If tree is null or is single node only, return null (no second largest)
  if (root==null || (root.left==null && root.right==null) return null;
  Node parent = null, child = root;
  // find the right most child
  while (child.right!=null) {
      parent = child;
      child = child.right;
   }
   // if the right most child has no left child, then it's parent is second largest
   if (child.left==null) return parent;
   // otherwise, return left child's rightmost child as second largest
   child = child.left;
   while (child.right!=null) child = child.right;
   return child;
}

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas