package validbst;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

/**
 * https://oj.leetcode.com/problems/validate-binary-search-tree/
 * 
 * Given a binary tree, determine if it is a valid binary search tree (BST).
 * Assume a BST is defined as follows:
 * - The left subtree of a node contains only nodes with keys less than the node's key.
 * - The right subtree of a node contains only nodes with keys greater than the node's key.
 * - Both the left and right subtrees must also be binary search trees
 * 
 */
public class Solution {
	
	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
		public String toString() {
			
			return "node: " + val + " (l:"
					+ (left != null ? left.val : "null")
					+ ", r:"
					+ (right != null ? right.val : "null")
					+ ")";
		
		}
	}
	
	public boolean isValidBST(TreeNode root) {
		List<TreeNode> path = new ArrayList<TreeNode>();
		return isValidBST(root, path);
    }
	
	private boolean isValidBST(TreeNode node, List<TreeNode> path) {
		if (node == null) return true;
		
		boolean isValid = true;
		
		int val = node.val;
		
		ListIterator<TreeNode> lit = path.listIterator(path.size());
		TreeNode current = node;
		while (lit.hasPrevious()) {
			TreeNode parent = lit.previous();
			if (current == parent.right) {
				if (val <= parent.val) {
					isValid = false;
				}
			}
			else {
				if (val >= parent.val) {
					System.out.println("invalid: " + node);
					isValid = false;
				}
			}
			current = parent;
			if (!isValid) break;
		}
		
		if (isValid) {
			path.add(node);
			isValid  = isValidBST(node.left, path);
			isValid = isValid && isValidBST(node.right, path);
			path.remove(node);
		}
		
		return isValid;
	}
}

@@ -16,90 +16,8 @@
 t;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0Aimport java.util.ListIterator;%0A
 %0A/**
@@ -463,419 +463,526 @@
  %0A *
-/%0Apublic class Solution %7B%0A%09%0A%09static class TreeNode %7B%0A%09%09int val;%0A%09%09TreeNode left;%0A%09%09TreeNode right;%0A%09%09TreeNode(int x) %7B val = x; %7D%0A%09%09public String toString() %7B%0A%09%09%09%0A%09%09%09return %22node: %22 + val + %22 (l:%22%0A%09%09%09%09%09+ (left != null ? left.val : %22null%22)%0A%09%09%09%09%09+ %22, r:%22%0A%09%09%09%09%09+ (right != null ? right.val : %22null%22)%0A%09%09%09%09%09+ %22)%22;%0A%09%09%0A%09%09%7D%0A%09%7D%0A%09%0A%09public boolean isValidBST(TreeNode root) %7B%0A%09%09List%3CTreeNode%3E path = new ArrayList%3C
+ My first solution involved keeping track of the complete path from the root%0A * which is unnecessary since all is needed is the min and max allowable values%0A * for a given node, defined by its ancestry as follows:%0A * - for the left child: the max is the immediate parent's value, the min is the same than the parent%0A *  -for the right child: the max is the same than the parent's max, the min is the immediate parent's value%0A */%0Apublic class Solution %7B%0A%09%0A%09static class TreeNode %7B%0A%09%09int val;%0A%09%09TreeNode left;%0A%09%09
 TreeNode
 %3E();
@@ -981,810 +981,538 @@
 Node
-%3E()
+ right
 ;%0A%09%09
+T
 re
-turn isValidBST(root, path);%0A    %7D%0A%09%0A%09private boolean isValidBST(TreeNode node, List%3CTreeNode%3E path) %7B%0A%09%09if (node == null) return true;%0A%09%09%0A%09%09boolean isValid = true;%0A%09%09%0A%09%09int val = node.val;%0A%09%09%0A%09%09ListIterator%3CTreeNode%3E lit = path.listIterator(path.size());%0A%09%09TreeNode current = node;%0A%09%09while (lit.hasPrevious()) %7B%0A%09%09%09TreeNode parent = lit.previous();%0A%09%09%09if (current == parent.right
+eNode(int x) %7B val = x; %7D%0A%09%7D%0A%09%0A%09public boolean isValidBST(TreeNode root) %7B%0A%09%09// initialize recursion%0A%09%09return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);%0A    %7D%0A%09%0A%09// each node in a BST has a min and max which depend on the node's ancestry%0A%09private boolean isValidBST(TreeNode node, int min, int max
 ) %7B%0A
-%09%09
 %09%09if (
-val %3C= parent.val) %7B%0A%09%09%09%09%09isValid = fals
+node == null) %7B%0A%09%09%09return tru
 e;%0A
-%09%09
 %09%09%7D%0A%09%09
-%09%7D
 %0A%09%09
-%09else %7B%0A%09%09%09%09if (val %3E= parent.val) %7B%0A%09%09%09%09%09System.out.println(%22invalid: %22 + node);%0A%09%09%09%09%09isValid = false;%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%09current = parent;%0A%09%09%09if (!isValid) break;%0A%09%09%7D%0A%09%09%0A%09%09if (isValid) %7B%0A%09%09%09path.add(node);%0A%09%09%09isValid  = isValidBST(node.left, path);%0A%09%09%09isValid = isValid && isValidBST(node.right, path);%0A%09%09%09path.remove(node);%0A%09%09%7D%0A%09%09%0A%09%09return isValid
+if (node.val %3C= min %7C%7C node.val %3E= max) %7B%0A%09%09%09return false;%0A%09%09%7D%0A%09%09%0A%09%09return isValidBST(node.left,  min ,node.val)%0A%09%09%09&& isValidBST(node.right, node.val, max)
 ;%0A%09%7D

provided better solution for valid bst