# [NineChap 3.3] Binary Search Tree

## Question list

BST

1. Recover Binary Search Tree - used global variable

2. Convert Sorted Array to Binary Search Tree

3. Convert Sorted List to Binary Search Tree - used global variable

## Code

Validate Binary Search Tree

``````public boolean isValidBST(TreeNode root) {
return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean validate(TreeNode node, int min, int max) {
if (node == null) {
return true;
}
if (node.val <= min || max <= node.val) {
return false;
}
return validate(node.left, min, node.val) & validate(node.right, node.val, max);
}
``````

Insert a Node in Binary Search Tree and Delete a Node in Binary Search Tree are written in a new post.

Search Range in a Binary Search Tree

There is a new post for this.

Recover Binary Search Tree

``````// 3 global variables used
TreeNode first = null;
TreeNode second = null;
TreeNode current = null;

public void recoverTree(TreeNode root) {
traverse(root);
if (first != null) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}

public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
// inorder traversal
if (current != null && current.val > root.val) {
if (first == null) {
first = current;
}
second = root;
}
current = root;
traverse(root.right);
}
``````

Convert Sorted Array to Binary Search Tree

``````public TreeNode sortedArrayToBST(int[] num) {
if (num == null || num.length == 0) {
return null;
}
return build(num, 0, num.length - 1);
}

private TreeNode build(int[] num, int start, int end) {
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;
head.left = build(num, start, mid - 1);
head.right = build(num, mid + 1, end);
}
``````

Convert Sorted List to Binary Search Tree - note that this solution uses 1 global variable

``````ListNode cur = null;

// count total length of the list
int count = 0;
while (p != null) {
p = p.next;
count++;
}
// start to traverse the tree and fill in data
return build(0, count - 1);
}

private TreeNode build(int start, int end) {
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;