## Disordered Binary Search Trees

### March 10, 2017

As in the past, a binary tree is a list of three nodes with the value in the `car`, the left child in the `cadr`, and the right child in the `caddr`.

A null tree is a binary search tree. A non-null tree is a binary search tree if its left child is a binary search tree, its right child is a binary search tree, its node value is greater the head of its left child, and its node value is less than the head of its right child:

```(define (ordered? lt? tree)
(or (null? tree)

Here are two examples:

```> (ordered? < '(4 (0 () (1 () (2 () (3 () ())))) (5 () (6 () ())))) #t > (ordered? < '(6 (0 () (1 () (2 () (3 () ())))) (5 () (4 () ()))))
#f```

You can run the program at http://ideone.com/i7MGDU.

Pages: 1 2

### 4 Responses to “Disordered Binary Search Trees”

1. Paul said

@programmingpraxis: If I understand your definition of a BST given in the solution, then the following tree would be a BST:

├── 10 (root)
│ ├── 40
│ └── 5
│ ├── 20
│ └── 1

The tree at the left (with root value 5 and children 1 and 20) is a BST, but the total tree is not, as in the left tree the value 20 is higher than 10.

Below an iterative solution in Python. Recursive is not a good idea for this in Python, because it would not work for large trees.

```def is_bst(root):
Q = [(root, -inf, inf)]
while Q:
node, lo, hi = Q.pop()
if not node:
continue
if not lo < node.value < hi:
return False
Q += [(node.lft, lo, node.value), (node.rgt, node.value, hi)]
return True
```
2. Paul said

Unfortunately the tree is not printing well (it does in “preview”). The tree is:
root: 10 with children 5 and 40
left child of root: 5 with children 1 and 20

3. Paul said

ANother try to print the tree

```├── 10
│   ├── 40
│   └── 5
│       ├── 20
│       └── 1
```
4. Daniel said

An in-order traversal of a valid binary search tree will visit the nodes in sorted order. An in-order traversal of an invalid binary search tree will visit the nodes in unsorted order.

Here’s a solution in Java that validates a binary search tree by considering whether nodes visited in-order are sorted. Morris traversal is used for O(1) space, O(n) runtime.

The example checks a valid and invalid tree.

```public class BinarySearchTree<T extends Comparable<T>> {
class Node {
T value;
Node left;
Node right;

Node(T value) {
this.value = value;
}
}

Node root;

private Node insert(Node node, Node root) {
if (root == null) return node;
int compare = node.value.compareTo(root.value);
if (compare <= 0) {
root.left = insert(node, root.left);
} else {
root.right = insert(node, root.right);
}
return root;
}

Node insert(T value) {
Node node = new Node(value);
root = insert(node, root);
return node;
}

class Validator {
T lastValue;
boolean validate(T value) {
boolean valid = true;
if (lastValue != null) {
if (value.compareTo(lastValue) < 0) {
valid = false;
}
}
lastValue = value;
return valid;
}
}

boolean valid() {
Validator validator = new Validator();
Node node = root;
while (node != null) {
if (node.left == null) {
if (!validator.validate(node.value)) {
return false;
}
node = node.right;
} else {
Node predecessor = node.left;
while (predecessor.right != null && node != predecessor.right) {
predecessor = predecessor.right;
}
if (node == predecessor.right) {
if (!validator.validate(node.value)) {
return false;
}
predecessor.right = null;
node = node.right;
} else {
predecessor.right = node;
node = node.left;
}
}
}
return true;
}

public String toString(String prefix, Node node, boolean right) {
if (node == null) return "";
StringBuffer sb = new StringBuffer();
sb.append(toString(prefix + (right ? "    " : "│   "), node.right, true));
sb.append(prefix + (right ? "┌── " : "└── ") + node.value + "\n");
sb.append(toString(prefix + (right ? "│   " : "    "), node.left, false));
return sb.toString();
}

public String toString() {
}

public static void main(String[] args) {
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
int[] values = {43,2,5,42,12,672,3,34};
BinarySearchTree.Node[] nodes = new BinarySearchTree.Node[values.length];
for (int i = 0; i < values.length; ++i) {
nodes[i] = bst.insert(values[i]);
}
System.out.println("Original");
System.out.print(bst);
System.out.format("Valid: %s\n", bst.valid());

// Modify tree to invalidate
bst.root.left.value = bst.root.value + 1;
System.out.println();
System.out.println("Modified");
System.out.print(bst);
System.out.format("Valid: %s\n", bst.valid());
}
}
```

Output:

```Original
│   ┌── 672
└── 43
│       ┌── 42
│       │   │   ┌── 34
│       │   └── 12
│   ┌── 5
│   │   └── 3
└── 2
Valid: true

Modified
│   ┌── 672
└── 43
│       ┌── 42
│       │   │   ┌── 34
│       │   └── 12
│   ┌── 5
│   │   └── 3
└── 44
Valid: false
```