Select a Random Node from a Binary Tree with Equal Probability

Problem

Given a binary tree, return a random node such that each node has an equal probability of being selected.

Examples

Example 1

Input: root = [1,2,3,4,5]
Output: 3 (any node, uniformly random)
Explanation: Each node has 1/5 probability to be picked.

Example 2

Input: root = [10,20,30]
Output: 20 (any node, uniformly random)
Explanation: Each node has 1/3 probability to be picked.

Solution

Method 1 – Reservoir Sampling (Single Node)

Intuition

Reservoir sampling allows us to select a single node from a binary tree with equal probability, even if the total number of nodes is unknown or very large. By updating our selection as we traverse, we guarantee uniform selection for each node.

Approach

1. Traverse the tree (DFS or BFS).
2. Keep a counter idx for the number of nodes seen so far.
3. For each node:
   • Increment idx.
   • With probability 1/idx, select the current node as the answer.
4. After traversal, return the selected node.

Code

C++

class Solution {
public:
  TreeNode* getRandomNode(TreeNode* root) {
    TreeNode* ans = nullptr;
    int idx = 0;
    function<void(TreeNode*)> dfs = [&](TreeNode* node) {
      if (!node) return;
      idx++;
      if (rand() % idx == 0) ans = node;
      dfs(node->left);
      dfs(node->right);
    };
    dfs(root);
    return ans;
  }
};

Go

func GetRandomNode(root *TreeNode) *TreeNode {
  var ans *TreeNode
  idx := 0
  var dfs func(node *TreeNode)
  dfs = func(node *TreeNode) {
    if node == nil { return }
    idx++
    if rand.Intn(idx) == 0 {
      ans = node
    }
    dfs(node.Left)
    dfs(node.Right)
  }
  dfs(root)
  return ans
}

Java

class Solution {
  private TreeNode ans;
  private int idx;
  public TreeNode getRandomNode(TreeNode root) {
    ans = null;
    idx = 0;
    dfs(root);
    return ans;
  }
  private void dfs(TreeNode node) {
    if (node == null) return;
    idx++;
    if ((int)(Math.random() * idx) == 0) ans = node;
    dfs(node.left);
    dfs(node.right);
  }
}

Kotlin

class Solution {
  private var ans: TreeNode? = null
  private var idx = 0
  fun getRandomNode(root: TreeNode?): TreeNode? {
    ans = null
    idx = 0
    fun dfs(node: TreeNode?) {
      if (node == null) return
      idx++
      if ((0..idx-1).random() == 0) ans = node
      dfs(node.left)
      dfs(node.right)
    }
    dfs(root)
    return ans
  }
}

Python

from typing import Optional
import random

class Solution:
  def get_random_node(self, root: 'TreeNode') -> Optional['TreeNode']:
    ans = None
    idx = 0
    def dfs(node: Optional['TreeNode']):
      nonlocal ans, idx
      if not node:
        return
      idx += 1
      if random.randint(1, idx) == 1:
        ans = node
      dfs(node.left)
      dfs(node.right)
    dfs(root)
    return ans

Rust

use rand::Rng;
impl Solution {
  pub fn get_random_node(root: &TreeNode) -> Option<&TreeNode> {
    let mut ans = None;
    let mut idx = 0;
    fn dfs(node: &TreeNode, idx: &mut usize, ans: &mut Option<&TreeNode>) {
      *idx += 1;
      let mut rng = rand::thread_rng();
      if rng.gen_range(0..*idx) == 0 {
        *ans = Some(node);
      }
      if let Some(left) = &node.left {
        dfs(left, idx, ans);
      }
      if let Some(right) = &node.right {
        dfs(right, idx, ans);
      }
    }
    dfs(root, &mut idx, &mut ans);
    ans
  }
}

TypeScript

class Solution {
  getRandomNode(root: TreeNode): TreeNode | null {
    let ans: TreeNode | null = null;
    let idx = 0;
    function dfs(node: TreeNode | null) {
      if (!node) return;
      idx++;
      if (Math.floor(Math.random() * idx) === 0) ans = node;
      dfs(node.left);
      dfs(node.right);
    }
    dfs(root);
    return ans;
  }
}

Complexity

• ⏰ Time complexity: O(n) — Every node in the tree is visited exactly once during traversal.
• 🧺 Space complexity: O(h) — The recursion stack uses up to O(h) space, where h is the height of the tree.