Coderust: Hacking the Coding Interview/

...

/

Is a Binary Search Tree Valid?

Is a Binary Search Tree Valid?

Given a binary tree, determine whether it's a valid binary search tree.

We'll cover the following...

Statement

Given a binary tree, figure out whether it’s a valid binary search tree.

In a BST, each node’s key value is smaller than the key value of the right subtree nodes and greater than the key values of the left subtree nodes.

Example

The following binary tree is an example of a valid BST:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node5 125 node2->node5 node6 350 node2->node6

The following binary trees are not valid BSTs:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node5 90 node2->node5 node6 300 node2->node6 root2 100 node12 50 root2->node12 node22 200 root2->node22 node32 25 node12->node32 node42 110 node12->node42 node52 150 node22->node52 node62 300 node22->node62

Sample Input

The input list below represents the level-order traversal of the valid binary search tree above:

[100, 50, 200, 25, 75, 125, 350]

Expected Output

Yes

Constraints

We can assume the following constraints:

  • INT.MIN < Node Value < INT.MAX

Try it yourself

Note: The binary tree node’s class has members left and right to store references to other nodes, along with the member data to hold the node’s value.

main.cpp
BinaryTree.cpp
BinaryTreeNode.cpp
#include "BinaryTree.cpp"
using namespace std;
bool IsBst(BinaryTreeNode* root) {
	// TODO: Write - Your - Code
	return false;
}

Solution 1: Naive

The first solution that comes to mind is a naive one. We need to recursively check whether each node’s left subtree’s maximum value is less than its data, and its right subtree’s minimum value is greater than its data. Here are the steps we need to follow on each recursive call:

  • The base case checks and returns true if the node passed is null.
  • Iterate only through the left children of the left subtree to get the minimum node of the left subtree.
  • Iterate only through the right children of the right subtree to get the maximum node of the right subtree.
  • If the current node’s value is less than the minimum value of the left subtree or if the current node’s value is greater than the maximum value of the right subtree, return FALSE.
  • Make a recursive call on both the left and right children of the current node.

This algorithm is highly inefficient as we explore both the right and left subtrees for each node.

Time complexity

The time complexity of this solution is quadratic, O(n2)O(n^{2}) ...