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)
      (and (ordered? lt? (cadr tree))
           (ordered? lt? (caddr tree))
           (or (null? (cadr tree))
               (lt? (caadr tree) (car tree)))
           (or (null? (caddr tree))
               (lt? (car tree) (caaddr 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.

Advertisements

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() {
            return toString("", root, false);
        }
    
        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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: