Cracking The Coding Interview Together – Problem 4.11: Random Node

You're tasked with building a custom binary tree, complete with insert, find, and delete. But there's a twist: you also need a getRandomNode() method that returns any node with equal probability. This isn't a trivial addition; it forces us to consider how to maintain randomness and efficiency across all operations without compromising our tree's performance. Our goal today is to design and implement a robust binary tree that elegantly handles this unique getRandomNode() requirement.

Problem Statement

Random Node: You are implementing a binary tree class from scratch which, in addition to insert, find, and delete, has a method getRandomNode() which returns a random node from the tree. All nodes should be equally likely to be returned. Design and implement an algorithm for getRandomNode, and explain how you would implement the rest of the methods.

Implement a binary tree class supporting insert(value), find(value), and delete(value). Additionally, implement getRandomNode(), which returns a random node from the tree, ensuring all nodes have an equal likelihood of being selected. We'll design the algorithm for getRandomNode() and explain how the other methods integrate to support it efficiently.

Analyze the Problem Together

Achieving equal probability for getRandomNode() efficiently is the core. Naive approaches like converting the tree to a list (O(N) for getRandomNode()) or maintaining a separate synchronized list (O(N) for delete()) are inefficient and undermine the tree's O(log N) potential.

The "Aha!" moment is augmenting our TreeNode. By adding a size property (the count of nodes in its subtree), we gain the ability to "index" into the tree. This allows probabilistic decisions at each node, guiding us to a random node in O(log N) time (on average), while keeping insert and delete efficient by updating sizes on the recursion's return path.

Questions for the Interviewer

As a senior engineer, we'd clarify:

• Operation frequencies (insert, delete, find, getRandomNode)?
• Maximum node count? (Memory, balancing needs)
• Are duplicate values allowed and how are they handled?
• Is the tree expected to remain balanced, or should we consider a self-balancing BST?

Think About the Solution

Our solution augments each TreeNode with an int size property, tracking total nodes in its subtree.

• TreeNode: Stores data, left, right, and size. Includes a helper updateSize().
• BinaryTree: Manages the root and a java.util.Random instance.

Core Logic:

• insert(value) & delete(value): Standard BST logic. Crucially, updateSize() is called on each node on the way up the recursion stack to maintain accurate subtree counts.
• getRandomNode(): Generates a random index within the current node's size. Compares index to the left child's size (leftSize): if index < leftSize, go left; if index == leftSize, return current node; else, go right, adjusting index for the right subtree.

Write Code and Explain

Here's the Java implementation:

import java.util.Random;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    int size; // Number of nodes in this subtree

    public TreeNode(int data) {
        this.data = data;
        this.size = 1;
    }

    private int getSize(TreeNode node) {
        return node == null ? 0 : node.size;
    }

    private void updateSize() {
        this.size = 1 + getSize(left) + getSize(right);
    }

    public TreeNode getRandomNode(Random random) {
        int leftSize = getSize(left);
        int index = random.nextInt(size); // Random index within this subtree

        if (index < leftSize) {
            return left.getRandomNode(random);
        } else if (index == leftSize) {
            return this;
        } else {
            return right.getRandomNode(random); // Adjust index for right subtree
        }
    }

    // findMin helper for deletion
    private TreeNode findMin() {
        if (left == null) {
            return this;
        }
        return left.findMin();
    }
}

class BinaryTree {
    TreeNode root;
    private Random random;

    public BinaryTree() {
        this.random = new Random();
    }

    public void insert(int value) {
        root = insert(root, value);
    }

    private TreeNode insert(TreeNode node, int value) {
        if (node == null) {
            return new TreeNode(value);
        }
        if (value <= node.data) {
            node.left = insert(node.left, value);
        } else {
            node.right = insert(node.right, value);
        }
        node.updateSize(); // Update size on return path
        return node;
    }

    public TreeNode find(int value) {
        return find(root, value);
    }

    private TreeNode find(TreeNode node, int value) {
        if (node == null || value == node.data) {
            return node;
        }
        return value < node.data ? find(node.left, value) : find(node.right, value);
    }

    public TreeNode getRandomNode() {
        if (root == null) {
            return null;
        }
        return root.getRandomNode(random);
    }

    public void delete(int value) {
        root = delete(root, value);
    }

    private TreeNode delete(TreeNode node, int value) {
        if (node == null) {
            return null; // Node not found
        }

        if (value < node.data) {
            node.left = delete(node.left, value);
        } else if (value > node.data) {
            node.right = delete(node.right, value);
        }
        else { // Found node to delete
            if (node.left == null) {
                return node.right; // Case 1: No left child
            } else if (node.right == null) {
                return node.left; // Case 1: No right child
            }
            // Case 2: Two children
            TreeNode successor = node.right.findMin();
            node.data = successor.data;
            node.right = delete(node.right, successor.data);
        }
        
        if (node != null) { // Only update size if node still exists
            node.updateSize();
        }
        return node;
    }

    // Helper for main method testing
    private int getSize(TreeNode node) { // Overloaded for BinaryTree class
        return node == null ? 0 : node.size;
    }

    public void inOrderTraversal() {
        inOrderTraversal(root);
        System.out.println();
    }

    private void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + "(" + node.size + ") ");
            inOrderTraversal(node.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.insert(50); tree.insert(30); tree.insert(70);
        tree.insert(20); tree.insert(40); tree.insert(60); tree.insert(80);

        System.out.print("Tree after insertions (data(size)): ");
        tree.inOrderTraversal(); 

        System.out.println("Random Nodes:");
        for (int i = 0; i < 3; i++) { 
            TreeNode randomNode = tree.getRandomNode();
            System.out.println("  Random node: " + (randomNode != null ? randomNode.data : "null"));
        }

        System.out.println("\nDeleting 30...");
        tree.delete(30);
        System.out.print("Tree after deleting 30: ");
        tree.inOrderTraversal(); 

        System.out.println("\nDeleting 50 (root)...");
        tree.delete(50);
        System.out.print("Tree after deleting 50: ");
        tree.inOrderTraversal(); 

        System.out.println("\nRandom Nodes after deletions:");
        for (int i = 0; i < 3; i++) { 
            TreeNode randomNode = tree.getRandomNode();
            System.out.println("  Random node: " + (randomNode != null ? randomNode.data : "null"));
        }
    }
}

Code Walkthrough:

We use TreeNode (with data, left, right, size) and BinaryTree classes. The size property, representing the count of nodes in a subtree, is key. updateSize() ensures this count is accurate.

• insert() & delete(): Standard BST operations. updateSize() is called on each node on the return path of recursive calls, propagating size changes up the tree.
• getRandomNode(): Leverages size. It generates a random index within the current node's subtree size. By comparing index to the left child's size, it deterministically decides whether the target random node is in the left subtree, the current node, or the right subtree (adjusting index for the right subtree). This ensures equal probability.

Time & Space Complexity

• All Operations (insert, find, delete, getRandomNode):
  • Time Complexity: O(log N) on average (balanced tree); O(N) worst case (skewed tree).
  • Space Complexity: O(log N) on average for recursion stack; O(N) worst case.
• Overall Space Complexity: O(N) for storing N nodes.

O(log N) performance relies on tree balance. Without self-balancing, performance can degrade.

Why This Problem Matters (The Senior Perspective)

This problem highlights critical engineering principles:

• Data Structure Augmentation: Extending structures (e.g., adding size to a node) for new, efficient operations.
• Trade-offs: Optimizing getRandomNode() required slightly more complex insert/delete logic.
• Real-world Applications: Random sampling (A/B testing, user selection), load balancing, game development.
• Production Considerations:
  • Self-Balancing: Essential for guaranteed O(log N) performance (AVL/Red-Black trees).
  • Thread Safety: Requires synchronization for concurrent access.
  • Persistence: Serialization must handle the augmented size property.
  • Randomness Quality: For critical apps, consider java.security.SecureRandom.

Final Thoughts

Implementing getRandomNode() is a superb exercise in data structure augmentation. By adding a simple size property, we transformed a potentially inefficient operation into an O(log N) one, while maintaining core tree operation performance. This problem underscores thoughtful design, trade-offs, and anticipating production concerns like balancing and concurrency.

Consider extending this: How would you implement getWeightedRandomNode()? What if this needed to scale across multiple machines? These challenges drive engineering growth.

Keep learning, keep building, and we'll catch you in the next deep dive!