Just No more free questions left!

Upgrade Now
**
Write a function to check that a binary tree is a valid binary search tree.
**

Here's a sample binary tree node class:

public static class BinaryTreeNode {
public int value;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
}
public BinaryTreeNode insertLeft(int leftValue) {
this.left = new BinaryTreeNode(leftValue);
return this.left;
}
public BinaryTreeNode insertRight(int rightValue) {
this.right = new BinaryTreeNode(rightValue);
return this.right;
}
}

Consider this example:

Loading...

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.

We'll never post on your wall or message your friends.

Once you're logged in, you'll get free full access to this and 4 other questions.

We'll never post on your wall or message your friends.

Once you're logged in, you'll get free full access to this and 4 other questions.

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 Integer.MIN_VALUE or Integer.MAX_VALUE appear in the input tree?

We'll never post on your wall or message your friends.

Once you're logged in, you'll get free full access to this and 4 other questions.

Code execution powered by Qualified.io

{"id":6361073,"username":"2017-10-21_14:16:03_iy!qow","email":null,"date_joined":"2017-10-21T14:16:03.467290+00:00","first_name":"","last_name":"","full_name":"","short_name":"friend","is_anonymous":true,"is_on_last_question":false,"percent_done":0,"num_questions_done":0,"num_questions_remaining":46,"recruiting_is_interested_in_intros":null,"is_full_access":false,"first_payment_date":null,"last_payment_date":null,"num_free_questions_left":3,"terms_has_agreed_to_latest":false,"preferred_content_language":"","preferred_editor_language":"","is_staff":false,"auth_providers_human_readable_list":"","num_auth_providers":0,"auth_email":"","profile_public_id":null}

. . .