Task 1

One of our students has recently been to a coding interview and was asked the following question:

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false

In Example-2, the root node's value is $5$ but its right child's value is $4$. Hence, it is not a valid BST.

Notice the input is provided as an array containing the level-order traversal of the values in a binary tree. If a level is not complete, it is padded with null values. You may assume the input will never be an empty array. For example, the edge case Input: [null] represents an empty binary tree which is by definition a valid (empty) binary search tree.

The starter code given to the student was as follows:

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {

  /**
   * Given a binary tree, determine if it is a valid binary search tree (BST).
   *
   * @param input An array containing the level order traversal of a binary tree.
   *              Pre: input != null
   * @return True if the given binary tree is a valid BST and false otherwise.
   */
  public static boolean isValidBst(Integer[] input) {
    Node root = constructTree(input);
    // TODO Implement me!
    return false; // stub
  }

  // Pre: input != null
  private static Node constructTree(Integer[] input) {
    int index = 0;
    Integer next = input[index++];
    Queue<Node> nodeQueue = new LinkedList<>();
    Node root = makeNode(next, nodeQueue);
    while (!nodeQueue.isEmpty() && index < input.length) {
      Node currentNode = nodeQueue.poll();
      next = input[index++];
      currentNode.left = makeNode(next, nodeQueue);
      if (index < input.length) {
        next = input[index++];
        currentNode.right = makeNode(next, nodeQueue);
      }
    }
    return root;
  }

  // Pre: queue != null
  private static Node makeNode(Integer val, Queue<Node> queue) {
    if (val != null) {
      Node node = new Node(val);
      queue.add(node);
      return node;
    }
    return null;
  }

  private static class Node {
    int val;
    Node left;
    Node right;

    Node(int val) {
      this.val = val;
    }
  }
}

The constructTree method (provided by the interviewer and we assume that it is correct) takes in the array containing the level-order traversal of a binary tree and it returns the root to the linked representation of the tree.

Open BinaryTree.java inside the task1 package in the starter code to see how the student solved this coding problem.

Your task is to test the implementation of BinaryTree.isValidBst. That is, test the student's solution.

Please write your tests in BinaryTreeTest.java file. It is entirely up to you what and how many tests you will write. Do as many as it takes to confidently accept the student's answer. On the other hand, it is sufficient to come up with one test that shows the solution is incorrect.

In the README.md file:

• If you found the solution to be correct, describe (briefly) the tests you've written (more about the ideas behind them, such as "I tested the solution for skewed binary tree, complete binary tree, etc") to accept the solution with confidence.
• If you found the solution to be incorrect, describe the test case in which the solution failed to hold to expectation, as well as the issue with the solution (i.e. why it failed the test). Note that you are not asked, in this case, to correct the solution.