A brief explantion of binary search trees and a simple Clojure implementation. Included is a function which tests whether a given tree is a BST.

bst-check.md

Binary Search Trees

A Binary Search Tree (BST) is a data structure consisting of nodes, each of which has a value and references to two other nodes; one with a value larger than the current node's value, and one with a value smaller. If there are no values larger (or smaller) than the value at the current node, then the reference contains the null pointer.

Consequentially, operations on binary trees are most naturally defined recursively. As such, Clojure is perfect for this week's task!

The time complexity of operations on binary trees such as searching, insertion and deletion, is O(logn) where n is the height of the tree! As such, it is important to keep the BST balanced (idea for another week's challenge?)

(ns bst-check.core
  (:gen-class))

(defn make-node
  ([less greater value]
   {:less less :greater greater :value value})
  ([value]
   (make-node nil nil value)))

(defn comparator-over-nodes
  "Returns a comparison function specific for values of tree nodes"
  ([func]
   (fn [node1 node2]
     (func (:value node1) (:value node2))))
  ([func & args]
   (comparator-over-nodes #(func args %))))

(def equals
  (comparator-over-nodes =))

(def greater-than
  (comparator-over-nodes >))

(def less-than
  (comparator-over-nodes <))

(defn height
  "Determines the depth of the BST"
  ([root count]
   (if root
     (max (height (:less root) (inc count))
          (height (:greater root) (inc count)))
     count))
  ([root]
   (height root 0)))

(defn insert-node
  "inserts a node into a BST"
  [root new-node]
  (if (nil? root)
    new-node
    (if (greater-than new-node root)
      (assoc root :greater (insert-node (:greater root) new-node))
      (assoc root :less (insert-node (:less root) new-node)))))

(defn bld-rand-tree
  "Creates a BST of depth target-height full of random floats"
  ([target-height]
   (bld-rand-tree target-height (make-node (rand))))
  ([target-height root]
   (if (>= target-height (height root))
     (bld-rand-tree target-height (insert-node root (make-node (rand))))
     root)))

(defn greatest
  [root]
  (if (:greater root)
    (greatest (:greater root))
    root))

(defn is-bst
  "Not only does this check to see if the value at each 'less' child of
  each node is less than the value at that node (and 'greater'), but it also
  checks that EVERY element to the 'less' of each node is less than that node.
  Otherwise, the tree is not a BST. Additionally, this function ensures that "
  ([root greaters lesss]
   (if root
     (every? identity
             [(if (every? (fn [a-min] (< (:value root) a-min)) lesss)
                (is-bst (:less root) greaters (conj lesss (:value root)))
                false)
              (if (every? (fn [a-max] (> (:value root) a-max)) greaters)
                (is-bst (:greater root) (conj greaters (:value root)) lesss)
                false)])
     true))
  ([root]
   (is-bst root [] [])))

(def my-tree
  (assoc (assoc (assoc (make-node 10)
                  :less (make-node 8))
           :greater (make-node 11))
    :greater (make-node 4)))

(def rand-bst
  (bld-rand-tree 5))

(defn hip-speech
  "To give this listing a bit of a more human element..."
  [bool]
  (if bool
    "yuh"
    "nah bruh"))

(defn -main
  "Demo this thing"
  [& args]
  (println (str "Is my-tree a BST? " (hip-speech (is-bst my-tree))))
  (println (str "Well what about rand-bst? " (hip-speech (is-bst rand-bst)))))