Expedia Group Interview Question: Write a function that determi... | Glassdoor

Interview Question

Senior Software Developer Interview Bellevue, WA

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

Answer

Interview Answer

3 Answers

3

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

Interview Candidate on Apr 1, 2011
0

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

Anon on May 7, 2011
0

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);
    }
}

Pur on Aug 14, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.