Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
public class Node {
...
public boolean isBST() {
boolean valid = true;
if (left != null) {
if (left.data <= data) {
valid = left.isBST();
} else {
return false;
}
}
if (!valid) {
return false;
}
if (right != null) {
if (right.data > data) {
valid = right.isBST();
} else {
return false;
}
}
return valid;
}
}
O(N) time, O(1) space
This is not O(1) space. You are using recursion, that means implicit method stacks.
Worst case space complexity O(N) -- In case it is a totally unbalanced binary search tree, like a linked list, the space complexity would be O(N) since all the nodes have to be traversed as part of successive recursion.
Average case space complexity: O(lg(n)) -- In case of a balanced binary search tree, the space complexity would be O(lg(n)). First all left, then all right.
Best case space complexity O(1) -- In case of a failure at early stages.
Here is the C++ solution of the question.
BST should have left side of trees smaller than parent and right side of trees larger than the parent.
After inorder search, checking if the order is preserved can tell whether the tree is BST.
#include <iostream>
#include <vector>
using namespace std;
struct node {
node* left;
node* right;
int value;
node(int v):value(v), left(0), right(0){}
};
vector<int> results;
void inorder(node *n)
{
if (!n)
return;
inorder(n->left);
results.push_back(n->value);
inorder(n->right);
}
bool check_order(vector<int>&result)
{
int ascending = INT_MIN;
for (int i = 1; i < result.size(); i++)
{
if (result[i-1]==result[i])
continue;
if (ascending == INT_MIN)
{
ascending = (result[i-1]< result[i]);
}else if (ascending != (result[i-1]<result[i]))
{
return false;
}
}
return true;
}
bool is_bst(node *r)
{
inorder(r);
return check_order(results);
}
int isBST(struct node* node) {
return(checkIsBST(node, INT_MIN, INT_MAX));
}
int checkIsBST(struct node* node, int min, int max) {
if (node==NULL)
return true;
if (node->data<min || node->data>max)
return false;
return
( checkIsBST(node->left, min, node->data) &&
checkIsBST(node->right, node->data+1, max) );
}
bool IsBST(const Node *root)
{
if (root == NULL) {
return true;
}
vector<int> elements;
return InorderOrderTravel(root, elements);
}
bool InorderOrderTravel(const Node *root, vector<int>& elements)
{
if (root == NULL) {
return true;
}
if (root->left != NULL &&
!InorderOrderTravel(root->left, elements)) {
return false;
}
// fast fail
if (elements.size() > 0 &&
elements[elements.size() - 1] > root->data) {
return false;
}
elements.push_back(root->data);
if (root->right != NULL &&
!InorderOrderTravel(root->right, elements)) {
return false;
}
return true;
}
class TreeNode {
var value: Int?
var leftChild: TreeNode?
var rightChild: TreeNode?
}
func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
print("value: " + String(node.value!))
print("min: " + String(min))
print("max: " + String(max))
if node.value! < min || node.value! > max
{
return false
}
if let leftChild = node.leftChild {
if isBST(leftChild, min: min, max: node.value!) == false {
return false
}
}
if let rightChild = node.rightChild {
if isBST(rightChild, min: node.value!, max: max) == false {
return false
}
}
return true
}
// Creating BST
let minValue = Int.min
let maxValue = Int.max
let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil
let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil
let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil
let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil
let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7
let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15
let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13
if isBST(node10, min: minValue, max: maxValue) == true {
print("Tree is BST.")
}else {
print("Tree is not BST.")
}
class TreeNode {
var value: Int?
var leftChild: TreeNode?
var rightChild: TreeNode?
}
func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
print("value: " + String(node.value!))
print("min: " + String(min))
print("max: " + String(max))
if node.value! < min || node.value! > max
{
return false
}
if let leftChild = node.leftChild {
if isBST(leftChild, min: min, max: node.value!) == false {
return false
}
}
if let rightChild = node.rightChild {
if isBST(rightChild, min: node.value!, max: max) == false {
return false
}
}
return true
}
// Creating BST
let minValue = Int.min
let maxValue = Int.max
let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil
let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil
let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil
let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil
let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7
let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15
let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13
if isBST(node10, min: minValue, max: maxValue) == true {
print("Tree is BST.")
}else {
print("Tree is not BST.")
}
class TreeNode {
var value: Int?
var leftChild: TreeNode?
var rightChild: TreeNode?
}
func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
print("value: " + String(node.value!))
print("min: " + String(min))
print("max: " + String(max))
if node.value! < min || node.value! > max
{
return false
}
if let leftChild = node.leftChild {
if isBST(leftChild, min: min, max: node.value!) == false {
return false
}
}
if let rightChild = node.rightChild {
if isBST(rightChild, min: node.value!, max: max) == false {
return false
}
}
return true
}
// Creating BST
let minValue = Int.min
let maxValue = Int.max
let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil
let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil
let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil
let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil
let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7
let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15
let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13
if isBST(node10, min: minValue, max: maxValue) == true {
print("Tree is BST.")
}else {
print("Tree is not BST.")
}
In-order traversal solution, O(1) space. you only need to remember the previous visited node.
struct Node {
Node* left, *right;
int val;
};
//global variable
bool foundFirst = false;
int previous = 0;
bool isBST(Node* root) {
if (root == NULL) return true;
if(isBST(root->left) ){
if(!foundFirst) {
foundFirst = true;
} else {
if (root->val < previous)
return false;
}
}
previous = root->val;
return isBST(root->right);
}
}
void inorder(Node node, ArrayList nodes) {
if (node != null) {
inorder(node.left, nodes);
nodes.add(node.value);
inorder(node.right, nodes);
}
}
boolean isBST(ArrayList<Integer> inorder) {
for(int i = 0; i < inorder.size() - 1; i++) {
if (inorder.get(0).compareTo(inorder.get(i + 1)) > 0){
return false;
}
}
return true;
}
Why is facebook ask such easy question? Just do inorder tree traversal and that is, everytime you traversal to it's own node, put that content into some data structure. Doesn't matter what it is. the data structure can be array, stack, queue. Then check the content in the data structure. For example, for stack, check and make sure every time you pop something from the stack, the next item you pop has to be less than or equal to the previous item it was pop. That it all.
- codealtecdown September 24, 2015