Interview Cake

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

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

Here's a sample binary tree implementation:

typedef struct BinaryTreeNode { void *value; struct BinaryTreeNode *left; struct BinaryTreeNode *right; } BinaryTreeNode; BinaryTreeNode * binaryTreeNodeNew(const void *value, size_t valueSize) { BinaryTreeNode *node; node = malloc(sizeof(BinaryTreeNode)); assert(node != NULL); node->value = malloc(valueSize); assert(node->value != NULL); memcpy(node->value, value, valueSize); node->left = NULL; node->right = NULL; return node; } BinaryTreeNode * binaryTreeNodeInsertLeft(BinaryTreeNode *treeRoot, const void *value, size_t valueSize) { treeRoot->left = binaryTreeNodeNew(value, valueSize); return treeRoot->left; } BinaryTreeNode * binaryTreeNodeInsertRight(BinaryTreeNode *treeRoot, const void *value, size_t valueSize) { treeRoot->right = binaryTreeNodeNew(value, valueSize); return treeRoot->right; } void binaryTreeNodeFree(BinaryTreeNode *treeRoot) { if (treeRoot != NULL) { binaryTreeNodeFree(treeRoot->left); binaryTreeNodeFree(treeRoot->right); free(treeRoot->value); free(treeRoot); } }

Our first thought might be to do an in-order traversal of the BST and return the second-to-last item. This means looking at every node in the BST. That would take time and space, where h is the max height of the tree (which is lg(n) if the tree is balanced, but could be as much as n if not).

We can do better than time and space.

We can do this in one walk from top to bottom of our BST. This means time (again, that's if the tree is balanced, otherwise).

A clean recursive implementation will take space in the call stack, but we can bring our algorithm down to space overall.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

We're doing one walk down our BST, which means time, where h is the height of the tree (again, that's if the tree is balanced, otherwise). space.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Reset editor

Powered by qualified.io

. . .