Most Common Item In A Binary Search Tree
July 18, 2017
This is a trick question: there is no O(n) solution. There can’t be because we need to look at all n keys in the tree, and accessing each key requires log n time in the best case (assuming the tree is balanced), so the best time complexity is O(n log n). So that’s what we implement.
We begin with a binary search tree that admits duplicate keys; it is a variant on the binary search tree of a previous exercise that did not admit duplicate keys:
(define (tree key lkid rkid) (vector key lkid rkid)) (define (key tree) (vector-ref tree 0)) (define (lkid tree) (vector-ref tree 1)) (define (rkid tree) (vector-ref tree 2)) (define nil (vector 'nil 'nil 'nil)) (vector-set! nil 1 nil) (vector-set! nil 2 nil) (define (nil? tree) (eqv? tree nil)) (define (insert lt? t k) (cond ((nil? t) (tree k nil nil)) ((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t))) ((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k))) (else (tree (key t) (insert lt? (lkid t) k) (rkid t)))))
We build a tree for testing:
> (define t (insert < nil 1)) > (set! t (insert < t 2)) > (set! t (insert < t 3)) > (set! t (insert < t 3)) > (set! t (insert < t 3)) > (set! t (insert < t 4)) > (set! t (insert < t 5)) > (set! t (insert < t 5)) > (set! t (insert < t 5)) > (set! t (insert < t 5)) > (set! t (insert < t 5)) > (set! t (insert < t 5)) > (set! t (insert < t 6)) > (set! t (insert < t 6)) > (set! t (insert < t 7)) > (set! t (insert < t 7)) > (set! t (insert < t 7))
Once the tree is built, we convert it to a list, make a frequency count with uniq-c, and find the largest count with maximum-by:
(define (enlist t)
(if (nil? t) (list)
(append (enlist (lkid t)) (list (key t)) (enlist (rkid t)))))
(define (uniq-c eql? xs)
(if (null? xs) xs
(let loop ((xs (cdr xs)) (prev (car xs)) (k 1) (result '()))
(cond ((null? xs) (reverse (cons (cons prev k) result)))
((eql? (car xs) prev) (loop (cdr xs) prev (+ k 1) result))
(else (loop (cdr xs) (car xs) 1 (cons (cons prev k) result)))))))
(define (maximum-by lt? . xs)
(let loop ((xs (cdr xs)) (current-max (car xs)))
(cond ((null? xs) current-max)
((lt? current-max (car xs))
(loop (cdr xs) (car xs)))
(else (loop (cdr xs) current-max)))))
Now we can find the most common item in a tree:
> (apply maximum-by (lambda (x y) (< (cdr x) (cdr y))) (uniq-c = (enlist t))) (5 . 6)
So the most common item is 5, which appears 6 times.
That takes O(n) space instead of O(1). We could use a generator instead, but having already broken the time bounds, we may as well take the easy approach of breaking the space bounds, too.
You can run the program at http://ideone.com/vGoAeF.
Assuming that the keys are ordered in such a way that equal keys will all be consecutive in an inorder traversal (as they would be for integers), doesn’t that suggest “inorder traversal -> find longest run of consecutive identical items”?
I think that would be something like pseudo-Haskell “maximumBy length . group . inorder” (tweaked to use O(1) space if necessary).
It seems to me that O(n) is possible. Walk the tree (O(n)) and count the occurences of all values (using a hash table).
We can certainly compute the desired result in O(n) time with a simple in-order traversal (or treefoldl), and a fixed set of variables (current,best) x (value,count). Where that falls down is in requiring O(depth(tree)) stack space. I suspect that we can get that down to O(1) space if we are allowed to smash the tree (flattening it to a list on the fly), but I am not sure. There is certainly no need for a hash table.
[…] written about binary search trees on several occasions, most recently here. Binary search trees are a fruitful source of exercises, and we have another one […]
Here’s a solution in Java. Morris traversal is used for in-order traversal (a recursive solution would require more than O(1) space). The sorted order of values from the in-order traversal is relied upon for tracking the mode.
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; } 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); } class ModeTracker { T maxValue; int maxCount = 0; T currentValue; int currentCount = 0; T mode() { return maxValue; } void update(T value) { if (currentValue != null && value.compareTo(currentValue) < 0) { throw new RuntimeException("Values must be passed in ascending order."); } if (value.equals(currentValue)) { currentCount++; } else { currentCount = 1; currentValue = value; } if (currentCount > maxCount) { maxCount = currentCount; maxValue = currentValue; } } } T mode() { if (root == null) return null; ModeTracker modeTracker = new ModeTracker(); Node node = root; while (node != null) { if (node.left == null) { modeTracker.update(node.value); node = node.right; } else { Node pred = node.left; while (pred.right != null && pred.right != node) { pred = pred.right; } if (pred.right == null) { pred.right = node; node = node.left; } else { pred.right = null; modeTracker.update(node.value); node = node.right; } } } return modeTracker.mode(); } public static void main(String[] args) { BinarySearchTree<Integer> bst = new BinarySearchTree<>(); int[] values = {43,2,5,42,5,12,4,3,5,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.print(bst); System.out.println(); Integer mode = bst.mode(); System.out.format("Mode: %d\n", mode); } }│ ┌── 672 └── 43 │ ┌── 42 │ │ │ ┌── 34 │ │ └── 12 │ ┌── 5 │ │ └── 5 │ │ │ ┌── 5 │ │ └── 4 │ │ └── 3 │ │ └── 3 └── 2 Mode: 5Example output follows the code in my last post.
My implementation with O(n) time and O(1) space in common lisp:
(defstruct btree num (left nil) (right nil)) (defun most-common-node-in-btree (tree) "Return the most common node in tree." (if (null tree) (values nil 0) ;; the following "let" includes all the space required -> O(1) (let ((common nil) (count 0) (key nil) (key-count 0) (node-center nil) (node-left nil) (node-right nil) (node-temp nil)) (setf node-center tree) (setf node-left (btree-left tree)) (setf node-right (btree-right tree)) (setf (btree-left node-center) nil) (labels ((handle-key (k) (cond ((equal k key) (incf key-count)) (t (when (>= key-count count) (if (> key-count count) (setf common (list key)) (setf common (cons key common))) (setf count key-count)) (setf key k) (setf key-count 1))))) (loop until (null node-center) ; loop through each node -> O(n) do (cond ((null node-left) (handle-key (btree-num node-center)) (cond ((null node-right) (setf node-center (btree-left node-center)) (when node-center (setf node-right (btree-right node-center)) (setf node-left nil))) (t (setf node-temp (btree-left node-center)) (setf node-center (btree-right node-center)) (setf node-left (btree-left node-center)) (setf node-right (btree-right node-center)) (setf (btree-left node-center) node-temp)))) (t (setf node-temp node-center) (setf node-center node-left) (setf node-left (btree-left node-center)) (setf node-right (btree-right node-center)) (setf (btree-left node-center) node-temp)))) (handle-key (list nil))) (values common count))))