Test if a Binary tree is BST or not

Question

Anonymous · Accepted Answer

--> Perform an inorder travesal on the BT and save the values in an array. 
--> Check if the array is sorted, if sorted then the binary tree is a BST.

mb · Answer

You don't need to store anything in an array. Just keep track if each next node is greater than the last while you traverse.

Liars Paradox · Answer

struct Node
{
	Node *left;
	Node *right;
	int item;
}

void InorderTraversal(Node n, int arr[])
{
	if(n!=NULL)
	{
		InorderTraversal(n.left);
		arr = n.item;
		arr++;
		InorderTraversal(n.right);
	}
}

bool isOrdered(int arr[])
{
	for(int i = 1; ia[i]) return false;
	return true;
}

int main()
{
	BT tree;
	int* arr = new int[tree.count];
	InorderTraversal(tree.node, arr);
	bool ordered = isOrdered(arr);
	if(ordered) cout<<"Tree being is ordered";
	else cout<<"Tree being is not ordered";
	delete[] arr;
	return 0;
}

Liars Paradox · Answer

struct Node
{
	Node *left;
	Node *right;
	int item;
}

void InorderTraversal(Node n, int arr[])
{
	if(n!=NULL)
	{
		InorderTraversal(n.left);
		arr = n.item;
		arr++;
		InorderTraversal(n.right);
	}
}

bool isOrdered(int arr[])
{
	for(int i = 1; ia[i]) return false;
	return true;
}

int main()
{
	BT tree;
	int* arr = new int[tree.count];
	InorderTraversal(tree.node, arr);
	bool ordered = isOrdered(arr);
	if(ordered) cout<<"Tree being is ordered";
	else cout<<"Tree being is not ordered";
	delete[] arr;
	return 0;
}

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches