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.

Advertisements

Pages: 1 2

7 Responses to “Most Common Item In A Binary Search Tree”

  1. Colin said

    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).

  2. Paul said

    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).

  3. 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.

  4. […] 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 […]

  5. Daniel said

    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: 5
    
  6. Daniel said

    Example output follows the code in my last post.

  7. kerson said

    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))))
    

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: