leetcode/problems/src/tree/ValidBinarySearchTree.java at master · KindleBooks66/leetcode · GitHub

History

64 lines (58 loc) · 1.77 KB

Raw

package tree;

/**

* Created by gouthamvidyapradhan on 09/03/2017. Given a binary tree, determine if it is a valid

* binary search tree (BST).

* <p>Assume a BST is defined as follows:

* <p>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. Example 1: 2 / \ 1 3 Binary tree [2,1,3], return

* true. Example 2: 1 / \ 2 3 Binary tree [1,2,3], return false.

public class ValidBinarySearchTree {

class Range {

long low, high;

}

static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

/**

* Main method

* @param args

* @throws Exception

public static void main(String[] args) throws Exception {

TreeNode root = new TreeNode(Integer.MIN_VALUE);

root.right = new TreeNode(Integer.MAX_VALUE);

System.out.println(new ValidBinarySearchTree().isValidBST(root));

}

private boolean isValidBST(TreeNode root) {

if (root == null || (root.right == null && root.left == null)) return true;

Range range = new Range();

range.high = Long.MAX_VALUE;

range.low = Long.MIN_VALUE;

return validate(root, range);

}

private boolean validate(TreeNode root, Range range) {

if ((root.val > range.low) && (root.val < range.high)) {

long temp = range.high;

if (root.left != null) {

range.high = root.val;

if (!validate(root.left, range)) return false;

}

if (root.right != null) {

range.high = temp;

range.low = root.val;

if (!validate(root.right, range)) return false;

}

return true;

} else return false;

}

leetcode/problems/src/tree/ValidBinarySearchTree.java at master · KindleBooks66/leetcode · GitHub

Uh oh!

Expand file tree

Breadcrumbs

ValidBinarySearchTree.java

Latest commit

History

Breadcrumbs

ValidBinarySearchTree.java

File metadata and controls