CODEWITHSUNDEEP
javabinary-tree
RK2015
RK2015

Reputation: 397

Randomly select a node from a Binary Tree

My tree class:

public class BT<E>{
   E value;
   BT<E> left, right;

   public BT(E value)
   {
      this.value=value;
   }   

   public BT (E value, BT left, BT right) 
   {
      this.value = value;
      this.left = left;
      this.right = right;
   }

How would I go about returning a random node from a tree after I have generated a tree? I know the depth and the number of nodes for every tree I generate.

Upvotes: 9

Views: 6184

Answers (4)

Eric
Eric

Reputation: 24954

First of all

The problem is also from book <Cracking the coding interview 6th>, at section: IX Interview Questions | 4. Trees and graphs | Question 4.11.

(It's a great book by Gayle Laakmann McDowell, a software engineer from Google, who has interviewed a lot people. )

Algorithms

  • (A) Make decision on random number, with subtree size recorded.

    Logic:

    • Impl binary tree node.

      • Each node has a size field.
        Indicate subtree size with this node as root.
      • It helps if each node has a parent field, that point to its parent node.

    • Impl binary tree, better be a BST.

      • On insert / detele, maintain the size & parent field of node.

    • BSTNode getRandomNode(BSTNode current, int rand)
      Compare rand with subtree size:

      Node<T> left = current.getLeft(); // left,
int leftSize = (left == null ? 0 : left.getSize()); // get size of left subtree,

if (rand == leftSize) return current; // current is chosen,
if (rand < leftSize) return randomNode(current.getLeft(), rand); // call on left subtree recursively,
else return randomNode(current.getRight(), rand - leftSize - 1); // call on right subtree recursively,
    • T getRandomNode(BST tree)
      • If tree is empty, return null.
      • Generate a random number, in range [0, size).
      • Call getRandomNode(tree.getRoot(), rand), and get random node.
      • Return random node's value.

    Complexity:

    • Time: O(h)
    • Space: O(1), (method stack use O(h))

    Where:

    • h is hight of tree.

  • (B) Put into list, access via random index.

    Logic:

    • Add tree nodes into a list, that support quick access via index.
    • When call the method, generate a random index in range [0, size), then get node at given index.

    Complexity:

    • Time: O(1) (If the tree is static)

    • Space: O(n)

    Where:

    • n is the size of tree.

    Tips:

    • If the tree is dynamic, then also need to maintain the array when tree changes.
      • When a node is removed from tree, also need to remove from array.
        This also takes O(n).
      • When a node is added to tree, also need to append to array.
        This takes O(1) if there are empty space left at end, but on array resize, it's O(n).

Compare 2 algorithms:

  • For a dynamic tree, A uses less memory, and runs faster. The winner for sure.
  • For a static tree, could also consider B, it could be faster when loopup, after the array is built.

Code

(Following is an implementation in Java using algorithm A mentioned above, with test case.)

RandomBST.java

import java.util.concurrent.ThreadLocalRandom;

/**
 * Random BST impl.
 *
 * @param <T>
 * @author eric
 * @date 2/10/19 5:02 PM
 */
public class RandomBST<T extends Comparable> extends BST<T> implements RandomBSTDesign<T> {
    @Override
    public void add(T v) {
        root = add((RandomBSTNode<T>) root, v, (RandomBSTNode<T>) root);
    }

    /**
     * Add to a subtree start from given node.
     *
     * @param current       root of a subtree to add node to,
     * @param currentParent parent of current,
     * @param v
     * @return the new root of subtree,
     */
    protected RandomBSTNode<T> add(RandomBSTNode<T> current, T v, RandomBSTNode<T> currentParent) {
        if (current == null) { // subtree is empty,
            RandomBSTNode<T> newNode = new RandomBSTNode<>(v, currentParent); // create new node,
            newNode.incSizeOfParents(); // increase size of parents,
            size++;
            return newNode;
        }

        // compare,
        int compareFlag = v.compareTo(current.value);

        // check this or subtree,
        if (compareFlag < 0) { // smaller, go to left subtree,
            current.left = add(current.getLeft(), v, current);
        } else if (compareFlag > 0) { // larger, go to right subtree,
            current.right = add(current.getRight(), v, current);
        } else { // equals, ignore it,
        }

        return current;
    }

    @Override
    protected RandomBSTNode<T> delete(BSTNode<T> current, T v) {
        return delete((RandomBSTNode<T>) current, v); // cast to subtype to call another method,
    }

    /**
     * Delete given value in subtree, if any.
     *
     * @param current
     * @param v
     * @return new root of the subtree
     */
    protected RandomBSTNode<T> delete(RandomBSTNode<T> current, T v) {
        if (current == null) return null;

        // compare,
        int compareFlag = v.compareTo(current.value);

        // check this or subtree,
        if (compareFlag < 0) { // smaller, go to left subtree,
            current.left = delete(current.left, v);
        } else if (compareFlag > 0) { // larger, go to right subtree,
            current.right = delete(current.right, v);
        } else { // equals, delete it,
            // no child,
            if (current.left == null && current.right == null) {
                current.decSizeOfParents(); // decrease size of parents,
                size--;
                return null;
            }

            // one child - right,
            if (current.left == null) {
                current.decSizeOfParents(); // decrease size of parents,
                size--;

                RandomBSTNode<T> randomRight = current.getRight(); // cast to subtype,
                randomRight.parent = current.parent;
                return randomRight;
            }
            // one child - left,
            if (current.right == null) {
                current.decSizeOfParents(); // decrease size of parents,
                size--;

                RandomBSTNode<T> randomLeft = (RandomBSTNode<T>) current.left; // cast to subtype,
                randomLeft.parent = current.parent;
                return randomLeft;
            }

            // 2 child,
            T smallestInRight = findSmallestValue(current.right);
            current.value = smallestInRight; // replace current with smallest in right subtree,
            current.right = delete(current.right, smallestInRight); // delete original smallest value in right subtree,
        }

        return current;

    }

    @Override
    public RandomBSTNode<T> getRoot() {
        return (RandomBSTNode<T>) root;
    }

    @Override
    public T randomValue() {
        if (size == 0) return null; // empty tree,

        int rand = ThreadLocalRandom.current().nextInt(size); // random value,
        RandomBSTNode rnode = randomNode(getRoot(), rand); // get random node,
        // System.out.printf("rand = %d, random node: %s\n", rand, rnode);

        return rnode == null ? null : (T) rnode.value;
    }

    protected RandomBSTNode randomNode(RandomBSTNode<T> current, int rand) {
        RandomBSTNode<T> left = current.getLeft(); // left,
        int leftSize = (left == null ? 0 : left.getSize()); // get size of left subtree,

        if (rand == leftSize) return current; // current is chosen,
        if (rand < leftSize) return randomNode(current.getLeft(), rand); // call on left subtree recursively,
        else return randomNode(current.getRight(), rand - leftSize - 1); // call on right subtree recursively,
    }

    /**
     * Random BST node impl.
     *
     * @param <T>
     */
    static class RandomBSTNode<T extends Comparable> extends BSTNode<T> implements RandomBSTNodeDesign<T> {
        protected int size; // size of subtree which has this node as root,
        protected RandomBSTNode<T> parent; // parent of this node, or null if this is root,

        public RandomBSTNode(T value, RandomBSTNode<T> parent) {
            this(value, 1, parent); // on creation, got size 1,
        }

        public RandomBSTNode(T value, int size, RandomBSTNode<T> parent) {
            super(value);
            this.size = size;
            this.parent = parent;
        }

        @Override
        public int incSize() {
            return ++size;
        }

        @Override
        public int decSize() {
            return --size;
        }

        @Override
        public void incSizeOfParents() {
            RandomBSTNode<T> pn = parent;
            while (pn != null) {
                pn.incSize();
                pn = pn.parent;
            }
        }

        @Override
        public void decSizeOfParents() {
            RandomBSTNode<T> pn = parent;
            while (pn != null) {
                pn.decSize();
                pn = pn.parent;
            }
        }

        @Override
        public boolean isRoot() {
            return parent == null;
        }

        @Override
        public RandomBSTNode<T> getLeft() {
            return (RandomBSTNode<T>) left;
        }

        @Override
        public RandomBSTNode<T> getRight() {
            return (RandomBSTNode<T>) right;
        }

        @Override
        public int getSize() {
            return size;
        }

        @Override
        public RandomBSTNode getParent() {
            return parent;
        }

        @Override
        protected void appendMoreToString(StringBuilder sb) {
            sb.append(", size = ").append(size); // size,
            sb.append(", parent value = ").append(parent == null ? null : parent.getValue()); // parent,
        }

        /*------ unsupported methods ------*/
        @Override
        void setLeft(BSTNode<T> left) {
            throw new UnsupportedOperationException("Should not set subtree directly, because size is difficult to maintain.");
        }

        @Override
        void setRight(BSTNode<T> right) {
            throw new UnsupportedOperationException("Should not set subtree directly, because size is difficult to maintain.");
        }
    }
}

RandomBSTTest.java (partly)
(unit test, via TestNG)

import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Consumer;

/**
 * RandomBST test.
 *
 * @author eric
 * @date 2/10/19 5:50 PM
 */
public class RandomBSTTest {
    private int n = 100;
    private int avgRound = (1 << 18); // avg round for each node, when get random value,

    private RandomBST<Integer> mbst; // minimal BST,
    private RandomBST<Integer> ebst; // empty BST,

    @BeforeMethod
    public void init() {
        // init minimal BST,
        mbst = CreateMinimalBST.createRandomFromNumRange(0, n);

        // init empty BST,
        ebst = new RandomBST<>();
    }

    // other non-random related test cases are removed,

    // randomValue()
    @Test
    public void testRandomValue() {
        int round = n * avgRound; // total round,
        System.out.printf("tree size: %d, total round: %d, result:\n", n, round);

        Map<Integer, Integer> freqMap = new LinkedHashMap<>();
        // init map,
        for (int i = 0; i < n; i++) {
            freqMap.put(i, 0);
        }

        // get random value & count frequency,
        for (int i = 0; i < round; i++) {
            int rv = mbst.randomValue();
            freqMap.put(rv, freqMap.get(rv) + 1);
        }

        double avgPercentage = 100 / n; // average percentage,
        // print result,
        for (int x : freqMap.keySet()) {
            int freq = freqMap.get(x);
            double percentage = freq * 100.0 / round;
            double diffPercentage = percentage - avgPercentage;
            System.out.printf("\trandom value: %2d, chosen count: %d, percentage: %.4f %%, differ: %.4f %%\n", x, freq, percentage, diffPercentage);
            Assert.assertTrue(Math.abs((freq - avgRound) * 1.0 / avgRound) <= 0.01); // differ <= 0.01, means <= 1 / 100,
        }

        // empty tree,
        Assert.assertNull(ebst.randomValue());
    }
}

(All test cases would pass.)

Output of test method testRandomValue():

tree size: 100, total round: 26214400, result:
    random value:  0, chosen count: 262162, percentage: 1.0001 %, differ: 0.0001 %
    random value:  1, chosen count: 262166, percentage: 1.0001 %, differ: 0.0001 %
    random value:  2, chosen count: 262897, percentage: 1.0029 %, differ: 0.0029 %
    random value:  3, chosen count: 261887, percentage: 0.9990 %, differ: -0.0010 %
    random value:  4, chosen count: 262428, percentage: 1.0011 %, differ: 0.0011 %
    random value:  5, chosen count: 262094, percentage: 0.9998 %, differ: -0.0002 %
    random value:  6, chosen count: 261662, percentage: 0.9982 %, differ: -0.0018 %
    random value:  7, chosen count: 262034, percentage: 0.9996 %, differ: -0.0004 %
    random value:  8, chosen count: 261218, percentage: 0.9965 %, differ: -0.0035 %
    random value:  9, chosen count: 262054, percentage: 0.9997 %, differ: -0.0003 %
    random value: 10, chosen count: 261821, percentage: 0.9988 %, differ: -0.0012 %
    random value: 11, chosen count: 262401, percentage: 1.0010 %, differ: 0.0010 %
    random value: 12, chosen count: 262056, percentage: 0.9997 %, differ: -0.0003 %
    random value: 13, chosen count: 262119, percentage: 0.9999 %, differ: -0.0001 %
    random value: 14, chosen count: 261878, percentage: 0.9990 %, differ: -0.0010 %
    random value: 15, chosen count: 262191, percentage: 1.0002 %, differ: 0.0002 %
    random value: 16, chosen count: 261224, percentage: 0.9965 %, differ: -0.0035 %
    random value: 17, chosen count: 262471, percentage: 1.0012 %, differ: 0.0012 %
    random value: 18, chosen count: 261906, percentage: 0.9991 %, differ: -0.0009 %
    random value: 19, chosen count: 262752, percentage: 1.0023 %, differ: 0.0023 %
    random value: 20, chosen count: 262762, percentage: 1.0024 %, differ: 0.0024 %
    random value: 21, chosen count: 262245, percentage: 1.0004 %, differ: 0.0004 %
    random value: 22, chosen count: 261942, percentage: 0.9992 %, differ: -0.0008 %
    random value: 23, chosen count: 262339, percentage: 1.0007 %, differ: 0.0007 %
    random value: 24, chosen count: 262266, percentage: 1.0005 %, differ: 0.0005 %
    random value: 25, chosen count: 261584, percentage: 0.9979 %, differ: -0.0021 %
    random value: 26, chosen count: 263036, percentage: 1.0034 %, differ: 0.0034 %
    random value: 27, chosen count: 261412, percentage: 0.9972 %, differ: -0.0028 %
    random value: 28, chosen count: 262305, percentage: 1.0006 %, differ: 0.0006 %
    random value: 29, chosen count: 261236, percentage: 0.9965 %, differ: -0.0035 %
    random value: 30, chosen count: 261681, percentage: 0.9982 %, differ: -0.0018 %
    random value: 31, chosen count: 262829, percentage: 1.0026 %, differ: 0.0026 %
    random value: 32, chosen count: 262411, percentage: 1.0010 %, differ: 0.0010 %
    random value: 33, chosen count: 263766, percentage: 1.0062 %, differ: 0.0062 %
    random value: 34, chosen count: 262448, percentage: 1.0012 %, differ: 0.0012 %
    random value: 35, chosen count: 262074, percentage: 0.9997 %, differ: -0.0003 %
    random value: 36, chosen count: 261986, percentage: 0.9994 %, differ: -0.0006 %
    random value: 37, chosen count: 261971, percentage: 0.9993 %, differ: -0.0007 %
    random value: 38, chosen count: 262403, percentage: 1.0010 %, differ: 0.0010 %
    random value: 39, chosen count: 261510, percentage: 0.9976 %, differ: -0.0024 %
    random value: 40, chosen count: 262020, percentage: 0.9995 %, differ: -0.0005 %
    random value: 41, chosen count: 262410, percentage: 1.0010 %, differ: 0.0010 %
    random value: 42, chosen count: 261910, percentage: 0.9991 %, differ: -0.0009 %
    random value: 43, chosen count: 262240, percentage: 1.0004 %, differ: 0.0004 %
    random value: 44, chosen count: 261923, percentage: 0.9992 %, differ: -0.0008 %
    random value: 45, chosen count: 261856, percentage: 0.9989 %, differ: -0.0011 %
    random value: 46, chosen count: 262708, percentage: 1.0022 %, differ: 0.0022 %
    random value: 47, chosen count: 262695, percentage: 1.0021 %, differ: 0.0021 %
    random value: 48, chosen count: 262882, percentage: 1.0028 %, differ: 0.0028 %
    random value: 49, chosen count: 262596, percentage: 1.0017 %, differ: 0.0017 %
    random value: 50, chosen count: 262872, percentage: 1.0028 %, differ: 0.0028 %
    random value: 51, chosen count: 262343, percentage: 1.0008 %, differ: 0.0008 %
    random value: 52, chosen count: 261969, percentage: 0.9993 %, differ: -0.0007 %
    random value: 53, chosen count: 261301, percentage: 0.9968 %, differ: -0.0032 %
    random value: 54, chosen count: 262206, percentage: 1.0002 %, differ: 0.0002 %
    random value: 55, chosen count: 261923, percentage: 0.9992 %, differ: -0.0008 %
    random value: 56, chosen count: 262577, percentage: 1.0017 %, differ: 0.0017 %
    random value: 57, chosen count: 262308, percentage: 1.0006 %, differ: 0.0006 %
    random value: 58, chosen count: 262600, percentage: 1.0017 %, differ: 0.0017 %
    random value: 59, chosen count: 261682, percentage: 0.9982 %, differ: -0.0018 %
    random value: 60, chosen count: 261983, percentage: 0.9994 %, differ: -0.0006 %
    random value: 61, chosen count: 262450, percentage: 1.0012 %, differ: 0.0012 %
    random value: 62, chosen count: 263582, percentage: 1.0055 %, differ: 0.0055 %
    random value: 63, chosen count: 261755, percentage: 0.9985 %, differ: -0.0015 %
    random value: 64, chosen count: 262773, percentage: 1.0024 %, differ: 0.0024 %
    random value: 65, chosen count: 261581, percentage: 0.9979 %, differ: -0.0021 %
    random value: 66, chosen count: 262071, percentage: 0.9997 %, differ: -0.0003 %
    random value: 67, chosen count: 262053, percentage: 0.9997 %, differ: -0.0003 %
    random value: 68, chosen count: 261491, percentage: 0.9975 %, differ: -0.0025 %
    random value: 69, chosen count: 261840, percentage: 0.9988 %, differ: -0.0012 %
    random value: 70, chosen count: 261837, percentage: 0.9988 %, differ: -0.0012 %
    random value: 71, chosen count: 262293, percentage: 1.0006 %, differ: 0.0006 %
    random value: 72, chosen count: 261928, percentage: 0.9992 %, differ: -0.0008 %
    random value: 73, chosen count: 260978, percentage: 0.9956 %, differ: -0.0044 %
    random value: 74, chosen count: 262260, percentage: 1.0004 %, differ: 0.0004 %
    random value: 75, chosen count: 262151, percentage: 1.0000 %, differ: 0.0000 %
    random value: 76, chosen count: 262981, percentage: 1.0032 %, differ: 0.0032 %
    random value: 77, chosen count: 261602, percentage: 0.9979 %, differ: -0.0021 %
    random value: 78, chosen count: 261938, percentage: 0.9992 %, differ: -0.0008 %
    random value: 79, chosen count: 262335, percentage: 1.0007 %, differ: 0.0007 %
    random value: 80, chosen count: 262213, percentage: 1.0003 %, differ: 0.0003 %
    random value: 81, chosen count: 262336, percentage: 1.0007 %, differ: 0.0007 %
    random value: 82, chosen count: 262356, percentage: 1.0008 %, differ: 0.0008 %
    random value: 83, chosen count: 261782, percentage: 0.9986 %, differ: -0.0014 %
    random value: 84, chosen count: 262610, percentage: 1.0018 %, differ: 0.0018 %
    random value: 85, chosen count: 261772, percentage: 0.9986 %, differ: -0.0014 %
    random value: 86, chosen count: 261874, percentage: 0.9990 %, differ: -0.0010 %
    random value: 87, chosen count: 262319, percentage: 1.0007 %, differ: 0.0007 %
    random value: 88, chosen count: 262144, percentage: 1.0000 %, differ: 0.0000 %
    random value: 89, chosen count: 261808, percentage: 0.9987 %, differ: -0.0013 %
    random value: 90, chosen count: 261980, percentage: 0.9994 %, differ: -0.0006 %
    random value: 91, chosen count: 261742, percentage: 0.9985 %, differ: -0.0015 %
    random value: 92, chosen count: 261994, percentage: 0.9994 %, differ: -0.0006 %
    random value: 93, chosen count: 262365, percentage: 1.0008 %, differ: 0.0008 %
    random value: 94, chosen count: 261954, percentage: 0.9993 %, differ: -0.0007 %
    random value: 95, chosen count: 261660, percentage: 0.9982 %, differ: -0.0018 %
    random value: 96, chosen count: 263220, percentage: 1.0041 %, differ: 0.0041 %
    random value: 97, chosen count: 261049, percentage: 0.9958 %, differ: -0.0042 %
    random value: 98, chosen count: 262000, percentage: 0.9995 %, differ: -0.0005 %
    random value: 99, chosen count: 262692, percentage: 1.0021 %, differ: 0.0021 %

===============================================
Default Suite
Total tests run: 1, Failures: 0, Skips: 0
===============================================

Relevant class & interface:

  • BST is a simple binary tree impl.

  • BSTNode is node impl of BST, contains fields: value / left / right.

  • RandomBSTDesign is interface for RandomBST.

  • RandomBSTDesign$RandomBSTNodeDesign is interface for RandomBST$RandomBSTNode.

  • RandomBST is random bst impl, extends BST, mainly override the add() / delete() method to maintain parent / size fields.

  • RandomBST$RandomBSTNode is node impl for RandomBST, extends BSTNode, and add fields: parent / size.

  • CreateMinimalBST is a tool that help to build a binary search tree of minimal height.

Upvotes: 4

iobender
iobender

Reputation: 3486

The algorithms from Dennis and Jeroen are simple to implement but O(n). I believe I have a O(log n) algorithm that is slightly more complicated.

Every node needs an equal chance of being selected. So at some tree T, let LN(T) be the number of nodes in the left tree, RN(T) be the number of nodes in the right tree, and N(T) be the number of total nodes, including this one (so N(T) = 1 + LN(T) + RN(T)). Select a random number R from 0 to N(T) - 1. If R == 0, return this node. If 1 <= R <= LT(N), recurse this method on the left subtree. Otherwise, recurse this method on the right subtree.

Untested code (assuming BT has a .size() method that works in O(1)):

public BT randomNode() {
    int r = new Random().nextInt(this.size());
    if (r == 0) {
        return this;
    } else if (left != null && 1 <= r && r <= left.size()) {
        return left.randomNode();
    } else {
        return right.randomNode();
    }
}

And of course you can do things like hoist the new Random() out of the method but the algorithm is the same.

Edit: fixed null pointer exception when left subtree was null.

Upvotes: 9

user5132172
user5132172

Reputation:

So use a Random Integer method and return an integer between 0 and the tree size.

Then do a breadth / depth first traversal on the tree, with a counter, that returns the node when it reaches the random integer.

Random rand = new Random();
int randomNum = rand.nextInt(treesize);
int count = -1;
Node randNode;

public static void getRandomTraversal(Node root){

    count++;

    if(count == randomNum)
        randNode = root;

    if(root.leftChild != null)
        getRandomTraversal(root.leftChild);

    if(root.rightChild != null)
        getRandomTraversal(root.rightChild);
}

Alternatively you could remove count as being global and add it as an argument to the recursive function. Though this is not as easy with binary trees when the tree has more than one child.

Upvotes: 6

Jeroen Vannevel
Jeroen Vannevel

Reputation: 44448

  1. Select a random number (new Random().nextInt(numberOfNodes))
  2. Walk through your tree however your like (depth first, breadth first, postorder, inorder, preorder)
  3. For each node you visit, increment a counter
  4. If the counter's value equals the randomly chosen number, pick that node

Upvotes: 3

Related Questions