Question

10d 10h left Java 7 1. Check the Structure Autocomplete Ready 1 > import java.io.*;... 10 ALL A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value, its node number in this case. A tree may either be: 11 class Result { * Complete the 'isValid' function below. • An empty tree, the root is null. • A non-empty tree with a non-null root node that contains a value and up to 2 subtrees, left and right, which are also binary trees. * The function is expected to return a STRING. * The function accepts INTEGER_ARRAY a as parameter. A binary tree is classified as a binary search tree (BST) if all of the non-null nodes exhibit two properties: public static String isValid List Integer // Write your code here • The left subtree of each node contains only nodes with values that are lower than its own value. •The right subtree of each node contains only nodes with values that are higher than its own value. ) { 25 } A pre-order traversal is a recursive tree traversal method where the current node is visited first, then the left subtree, and then the right subtree. The following pseudocode parses a tree into a list using pre-order traversal: 26 27 > public class Solution {... • If the root is null, return the null list. • For a non-null root node: 1. Create a pre-order traversal list, left, of the left subtree. 2. Create a pre-order traversal list, right, of the right subtree. 3. Return the concatenated list: the non-null node + left + right. Line: 10 col: 1 the root node van ons bedre mode in the many The root node will always be the first node in the array a. For example, given the tree a = [2, 1, 3, 4, 5), the root is at node 2. The 1 is encountered next and must be to the left of 2. That pare umple liver the re st 12, 1, 3, Test Results Festits Custom Input custom Run Run Submit Code Submit Code

Would appreciate the answer in the Java coding language please and thank you!

Answer 1

The code for required method is provided below in bold.

public static String isValid(List<Integer> elements) {

    // start build up the array with the elements.
    TreeElement root = new TreeElement(elements.get(0), null, null);

    // iterate over rest of the items and build BST.
    for (int index = 1; index < elements.size(); ++index) {

        int elementToAdd = elements.get(index);

        // insert the element to the node.
        insertElement(root, elementToAdd);
    }

    // Do a preorder traversal of the created node and store it in a list.
    List<Integer> preOrderedElementList = new ArrayList<>();
    preOrderBST(root, preOrderedElementList);

    // Check if the list generated is equal to the input provided to this method.
    if (elements.equals(preOrderedElementList)) {
        return "Yes";
    }

    return "No";
}

/**
 * This method is responsible for doing pre order traversal on the node and store the trversal in the list passed.
 * 
 * @param node
 * @param preOrderedElementList
 */
private static void preOrderBST(TreeElement node, List<Integer> preOrderedElementList) {

    if (node == null) {
        return;
    }

    preOrderedElementList.add(node.info);

    // move left.
    preOrderBST(node.left, preOrderedElementList);

    // move right.
    preOrderBST(node.right, preOrderedElementList);
}

/**
 * This method will insert the element to the node and return the updated node.
 * 
 * @param node
 * @param elementToAdd
 * @return
 */
private static TreeElement insertElement(TreeElement node, int elementToAdd) {

    // if the tree is empty, create and return the new node.
    if (node == null) {
        return new TreeElement(elementToAdd, null, null);
    }
    if (elementToAdd < node.info) {
        // go left.
        node.left = insertElement(node.left, elementToAdd);

    } else if (elementToAdd > node.info) {
        // go right.
        node.right = insertElement(node.right, elementToAdd);
    }
    return node;
}

// Define tree node structure
static class TreeElement {

    private int         info;
    private TreeElement left;
    private TreeElement right;

    TreeElement(int info, TreeElement left, TreeElement right) {
        this.info = info;
        this.left = left;
        this.right = right;
    }
}

Sample Input1:

Arrays.asList(2, 1, 3, 4, 5)

Output: Yes

Sample Input2:

Arrays.asList(3, 4, 5, 1, 2)

Output: No

The screenshot for running sample inputs is provided below.

public static void main(String[] args) { System.out.println(isValid(Arrays.asList( ...a: 2, 1, 3, 4, 5))); System.out.println(isValid(Arrays.asList...a: 3, 4, 5, 1, 2))); public static String isValid(List<Integer> elements) { // start build up the array with the elements. TreeElement root = new TreeElement(elements.get(o), left: null, right: null); // iterate over rest of the items and build BST. for (int index = 1; index < elements.size(); ++index) { int elementToAdd = elements.get(index); // insert the element to the node. incontclamantinent alomon Toddl. Valid /Library/Java/JavaVirtualMachines/jdk1.8.0_231.jdk/Contents/Home/bin/java ... Yes No