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 check that a binary tree is a valid 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); } }

Consider this example:

A binary tree. To the left of the root is a subtree with a node containing 30, its left child containing 20, and its right child (highlighted in blue) 60.

Notice that when you check the blue node against its parent, it seems correct. However, it's greater than the root, so it should be in the root's right subtree. So we see that checking a node against its parent isn't sufficient to prove that it's in the correct spot.

We can do this in time and additional space, where n is the number of nodes in our tree. Our additional space is if our tree is balanced.

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.

time and space.

The time cost is easy: for valid binary search trees, we’ll have to check all n nodes.

Space is a little more complicated. Because we’re doing a depth first search, nodeAndBoundsStack will hold at most d nodes where d is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is .

But we can also relate d to n. In a balanced tree, d is \log_{2}{n}. And the more unbalanced the tree gets, the closer d gets to n.

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to the stack at each step. When the traversal hits the rightmost node, the stack will hold half of the n total nodes in the tree. Half n is , so our worst case space cost is .

What if the input tree has duplicate values?

What if INT_MIN or INT_MAX appear in the input tree?

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

. . .