Write a function that determines if a tree is a BST or not

Question

Sigiloso · Accepted Answer

A good way to start out is to confirm the understanding of what a BST is. It's a tree where each node has 0,1, or 2 children. The left child is smaller and the right child is larger. The solution consists of traversing the tree recursively, and returning false, if the above rules are violated. True otherwise

Pur · Answer

package test;

public class CheckBST {
	static boolean isBST = false;
	static boolean continueCheck = true;

	private static void checkBST(Node root) {
		if (continueCheck) {
			Node left = root.getLeftNode();
			Node right = root.getRightNode();
			if (left.getValue() < root.getValue()
					&& root.getValue() < right.getValue()) {
				isBST = true;

				if (null != left.getLeftNode() || null != left.getRightNode()) {
					checkBST(left);
				}
				if (null != right.getLeftNode() || null != right.getRightNode()) {
					checkBST(right);
				}
			} else {
				isBST = false;
				continueCheck = false;
			}
		}
	}

	public static void main(String[] args) {
		Node left = new Node(2, new Node(1), new Node(3));
		Node right = new Node(6, new Node(9), new Node(7));
		Node root = new Node(4, left, right, true);
		checkBST(root);
		System.out.println("is BST ? ::" + isBST);
	}
}

Sigiloso · Answer

In these sorts of interviews you really need to drill down and understand what the interviewer is looking for.


A good way to simulate a real interview experience is to do a mock with one of the Expedia  Senior Software Engineer experts on Prepfully, rated super strongly on TrustPilot...


prepfully.com/practice-interviews

Anon · Answer

How would you validate if its not a BST because it has more than 2 children, using the recursion algo above?

Expedia Group

Pergunta de entrevista da empresa Expedia Group

Respostas da entrevista

Empresas seguidas

Buscas de vagas