Skip to content

Latest commit

 

History

History
18 lines (16 loc) · 768 Bytes

README.md

File metadata and controls

18 lines (16 loc) · 768 Bytes
Raw

Given a binary tree, randomly get a node.

This means each node has the same probability to be returned.

transfer into TreeNode[]

A naive way would be traverse the tree and transfer the tree nodes into an array. Then we know the size of the array and we have random access. We can do sampling.
time: O(n)

using iterator

time: O(n)
space: O(height) without parent pointer O(1) with parent pointer

divide & conquer

  • left subtree -> sample of the left subtree + weight of the left subtree

  • right subtree -> sample of the right subtree + weight of the right subtree

  • root

    [0, left.size - 1] [left.size, left.size + right.size -1] [root] left sample right sample root

time: O(n)
space: O(height)