fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3.  
  4. class BSTCheck
  5. {
  6.  /** basic binary tree Node with int value. */
  7. 	static class Node {
  8. 		Node left,
  9. 			right;
  10. 		int	val;
  11. 		public Node(int v) { val = v; }
  12. 		public Node(Node l, int val, Node r) {
  13. 			this(val);
  14. 			left = l;
  15. 			right = r;
  16. 		}
  17. 		@Override
  18. 		public String toString() { return "Node " + val; }
  19. 	}
  20.  /** Checks if the tree rooted at node is a valid binary search tree. */
  21. 	interface BinarySearchTreeCheck {
  22. 		/** @return {@code true} if the tree rooted at {@code node}
  23. 		 *   is a valid binary search tree. */
  24. 		boolean isBinarySearchTree(Node node);
  25. 	}
  26.  /** Checks if the tree rooted at a node is a valid binary search tree. */
  27. 	static class DataMember implements BinarySearchTreeCheck {
  28. 		int previous = Integer.MIN_VALUE;
  29. 	/** @return {@code true} if the tree rooted at {@code node}
  30. 	 *   is a valid binary search tree. */
  31. 		@Override
  32. 		public boolean isBinarySearchTree(Node node) {
  33. 	        return null == node
  34. 	        	|| isBinarySearchTree(node.left)
  35. 	        	   && previous <= node.val
  36. 	        	      && node.val == (previous = node.val) // abuse
  37. 	        	   && isBinarySearchTree(node.right);
  38. 		}
  39. 	}
  40.  /** Checks if the tree rooted at a node is a valid binary search tree. */
  41. 	static class TwoMethods implements BinarySearchTreeCheck {
  42. 	/** @return {@code true} if the tree rooted at {@code node}
  43. 	 *   is a valid binary search tree. */
  44. 		@Override
  45. 		public boolean isBinarySearchTree(Node node) {
  46. 			return isBinarySearchTree(Integer.MIN_VALUE, node);
  47. 		}
  48. 	/** @return {@code true} if the tree rooted at {@code node}
  49. 	 *   is a valid binary search tree
  50. 	 *   containing values no smaller than {@code previous}. */
  51. 		public boolean isBinarySearchTree(int previous, Node node) {
  52. 			return null == node
  53. 	        	|| isBinarySearchTree(previous, node.left)
  54. 	        	   && previous <= node.val
  55. 	        	   && isBinarySearchTree(node.val, node.right);
  56. 		}
  57. 	}	
  58.  
  59. 	public static void main(String[] args) {
  60.     // Build a valid BST.
  61.         Node variant = new Node(-2),
  62.         	root = new Node(new Node(null, -2, variant),
  63.         		0, new Node(2));
  64.         for (int i = -3 ; i < 2 ; i++) {
  65.         	variant.val = i;
  66.         	System.out.println(i + ": " +
  67.         		new DataMember().isBinarySearchTree(root)
  68.         		+ '/' + new TwoMethods().isBinarySearchTree(root));
  69.         }
  70. 	}
  71. }
Success #stdin #stdout 0.1s 320512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-3: false/false
-2: true/true
-1: true/true
0: true/true
1: false/true
https://ideone.com/XaOytr
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!