Amazon Interview Question: First explain what a tree, th... | Glassdoor

Interview Question

Software Development Engineer In Test Interview(Student Candidate) Seattle, WA

First explain what a tree, then binary tree, then a binary

  search tree is. Now implement a function that verifies whether a binary tree is a valid binary search tree.
Tags:
binary search tree, validation
Answer

Interview Answer

5 Answers

0

Sadly I ran out of time for this question. But I e-mailed the response after my time was up. First create a small implementation of a binary tree, I did it in java with the standard implementation Nodes with left and right children as data points. Check whether the left child and right child have valid values, which is to say make sure all children on the right of a node have values greater than parents that they came from. The key thing that I missed during the interview was the fact that if you traverse once to the right, then once to the left, you have to make sure the value is between the max and min that you've encountered up to that point.

Interview Candidate on Jan 27, 2012
0

int validate_BST(struct tnode *tree){
    int ret1, ret2;

    if (tree == NULL)
        return 1;
    else {
        if (tree->left != NULL){
           if (tree->data > tree-left->data){
               ret1 = validate_BSR(tree->left);
           }
           else
               return 0;

        }
        if (tree->right != NULL) {
            if (tree->data right->data){
                ret2 = vaidate_BSD(tree->right);
            }
            else
                return 0;
        }
        return (ret1 == 1 && ret2 == 1)? 1: 0;

    }
    return 0;
}

Tom on Feb 6, 2012
0

To find whether a binary tree is valid Binary search tree, do inorder traversal and check if the nodes are sorted.

Chetan on Jul 2, 2012
1

private boolean isBST(){

        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        private boolean isBST(Node node, int min, int max){

                if(node == null)
                        return true;

                if(node.data max)
                        return false;
                else
                        return (isBST(node.left, min, node.data) && isBST(node.right, node.data+1, max));

        }

double'o on Oct 19, 2012
0

In order to verify the Binary Search Tree, Read the nodes in Inorder mode. Also at every step check if the current node value is less than the one previously found then exit the traversal as the items are not sorted.

Vineet on Nov 1, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.