Most Common Item In A Binary Search Tree
July 18, 2017
Today’s exercise is an interview question:
You are given a binary search tree in which all keys in the left child of a node are less than or equal to the key of the current node and all keys in the right child of a node are greater than or equal to the key of the current node. Find the most common key in the binary search tree. You may use O(n) time and O(1) space.
Your task is to write a program to find the most common node in a binary search tree, subject to the given constraints. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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))))