Programming Praxis

4 Responses to “Disordered Binary Search Trees”

1. Paul said

   March 11, 2017 at 8:11 AM

   @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

   March 11, 2017 at 8:19 AM

   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

   March 11, 2017 at 8:21 AM

   ANother try to print the tree

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

   August 15, 2017 at 4:01 PM

   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