13. isBST1() Solution (Java). 14. isBST2() Solution (Java)

13. isBST1() Solution (Java)

/**
Tests if a tree meets the conditions to be a
binary search tree (BST).
*/
public boolean isBST() {
return(isBST(root));
}

/**
Recursive helper -- checks if a tree is a BST
using minValue() and maxValue() (not efficient).
*/
private boolean isBST(Node node) {
if (node==null) return(true);

// do the subtrees contain values that do not
// agree with the node?
if (node. left! =null & & maxValue(node. left) > node. data) return(false);
if (node. right! =null & & minValue(node. right) < = node. data) return(false);

// check that the subtrees themselves are ok
return( isBST(node. left) & & isBST(node. right) );
}

14. isBST2() Solution (Java)

/**
Tests if a tree meets the conditions to be a
binary search tree (BST). Uses the efficient
recursive helper.
*/
public boolean isBST2() {
return( isBST2(root, Integer. MIN_VALUE, Integer. MAX_VALUE) );
}

/**
Efficient BST helper -- Given a node, and min and max values,
recurs down the tree to verify that it is a BST, and that all
its nodes are within the min.. max range. Works in O(n) time --
visits each node only once.
*/
private boolean isBST2(Node node, int min, int max) {
if (node==null) {
return(true);
}
else {
// left should be in range min... node. data
boolean leftOk = isBST2(node. left, min, node. data);

// if the left is not ok, bail out
if (! leftOk) return(false);

// right should be in range node. data+1.. max
boolean rightOk = isBST2(node. right, node. data+1, max);

return(rightOk);
}
}

Java

//Java implementation to check if given Binary tree

//is a BST or not

/* Class containing left and right child of current

node and key value*/

class Node

{

int data;

Node left, right;

public Node(int item)

{

data = item;

left = right = null;

}

public class BinaryTree

{

//Root of the Binary Tree

Node root;

/* can give min and max value according to your code or

can write a function to find min and max value of tree. */

/* returns true if given search tree is binary

search tree (efficient version) */

boolean isBST() {

return isBSTUtil(root, Integer. MIN_VALUE,

Integer. MAX_VALUE);

}

/* Returns true if the given tree is a BST and its

values are > = min and < = max. */

boolean isBSTUtil(Node node, int min, int max)

{

/* an empty tree is BST */

if (node == null)

return true;

/* false if this node violates the min/max constraints */

if (node. data < min || node. data > max)

return false;

/* otherwise check the subtrees recursively

tightening the min/max constraints */

// Allow only distinct values

return (isBSTUtil(node. left, min, node. data-1) & &

isBSTUtil(node. right, node. data+1, max));

}

/* Driver program to test above functions */

public static void main(String args[])

{

BinaryTree tree = new BinaryTree();

tree. root = new Node(4);

tree. root. left = new Node(2);

tree. root. right = new Node(5);

tree. root. left. left = new Node(1);

tree. root. left. right = new Node(3);

if (tree. isBST())

System. out. println(" IS BST" );

else

System. out. println(" Not a BST" );

}

Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value

QUIZ: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

QUIZ: Given a binary search tree. Write a function that prints node values in descending order.

⇐ Предыдущая 1 23