Problem#
Given a binary tree, return a random node such that each node has an equal probability of being selected.
Examples#
Example 1#
1
2
3
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#
1
2
3
Input: root = [ 10 , 20 , 30 ]
Output: 20 ( any node, uniformly random)
Explanation: Each node has 1 / 3 probability to be picked.
Similar Problems
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#
Traverse the tree (DFS or BFS).
Keep a counter idx
for the number of nodes seen so far.
For each node:
Increment idx
.
With probability 1/idx
, select the current node as the answer.
After traversal, return the selected node.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.