Implement the following methoid in Q9 class which, tests whether a binary tree s
ID: 3598061 • Letter: I
Question
Implement the following methoid in Q9 class which, tests whether a binary tree satisfies the search tree order property at every mode.
public class Q9 {
/**
* Binary tree node
*/
public static class Node> {
private Key key; // key
private Node left, right; // links to subtrees
public Node(Key key) {
this.key = key;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
/**
* Check if the keys in the binary tree rooted with this node
* follow binary search tree order.
* It is okay to create another method and call that method here.
*
* Make sure the worst-case running time is linear, and explain
* why that is the case here.
*/
public static > boolean inSearchTreeOrder(Node node) {
//need help here
}
}
9. Implement the following method in Q9 class, which tests whether a binary tree satisfies the search tree order property at every node. Your implementation should have linear worst-case running time. Check if the keys in the binary tree rooted with this node It is okay to create another method and call that method here. Make sure the worst-case running time is linear, and explain *follow binary search tree order why that is the case here. public static boolean inSearchTree0rderNode node);Explanation / Answer
package dreamer;
public class Q9 {
/**
* Binary tree node
*/
public static class Node<Key extends Comparable<Key> > {
private Key key; // key
private Node left, right; // links to subtrees
public Node(Key key) {
this.key = key;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
public static <Key extends Comparable<Key>> boolean inSearchTreeOrderUtil(Node node, Node previous) {
//Check if node is not equal to null, We will Traverse Node in Inorder fashion
if (node != null)
{
//Call the above function recursively for left subtree i.e Inorder is LEFT, ROOT, RIGHT
if (!inSearchTreeOrderUtil(node.left, previous))
return false;
//If previous node is not null and previous node value is greater than the current element then its not a bst
if (previous != null && (node.key).compareTo(previous.key) <=0 )
return false;
//Assign PREVIOUS to current node
previous = node;
//Call the above function recursively for RIGHT subtree i.e Inorder is LEFT, ROOT, RIGHT
return inSearchTreeOrderUtil(node.right, previous);
}
return true;
}
/**
* Check if the keys in the binary tree rooted with this node follow binary
* search tree order. It is okay to create another method and call that
* method here.
*
* Make sure the worst-case running time is linear, and explain why that is
* the case here.
*/
public static <Key extends Comparable<Key>> boolean inSearchTreeOrder(Node node) {
//Initalise Prevoius Node as null
Node previous = null;
//Make call to Helper function
return inSearchTreeOrderUtil(node, previous);
}
}