Site Color
Text Color
Ad Color
Text Color
Evergreen
Duotone
Mysterious
Classic
or
A binary tree
The function count counts the number of nodes in all the subtrees and saves in the attribute size of the Node instance. The function get_random_node gets the random node of the tree. We have returned here the value of the random node.
import random # one pass in the whole tree to count the size of all the subtrees def count(root): if not root: return 0 return count(root.left) + 1 + count(root.right) # function to get the random node def get_random_node(root): a = root.size b = root.left.size if root.left else 0 c = root.right.size if root.right else 0 if b == c == 0: return root.val rand_num = random.randint(1, a) if rand_num <= b: return get_random_node(root.left) elif rand_num == b + 1: return root.val else: return get_random_node(root.right)
Let’s simulate the random events and see the percentage frequency of each node's value.
As expected, the percentage frequency is nearly the same for all the node values.
We do the proof of correctness here by induction.
The total number of nodes in the tree is n.
For any node in the tree, let a, b and c be the number of nodes in the subtree (containing the node), left subtree and right subtree respectively.
Differentiation is made between the selection and arrival process as the selection is selecting (and returning) the node whereas arrival is arriving at the node while traversing. Arrival at some node does not guarantee the selection of the node but arrival at some node is mandatory for the selection of the node.
First, let’s prove the randomness of the arrival process. Based on the randomness of the arrival process, we prove the randomness of the selection process.
Let’s suppose the arrival process is random up to some node. So, the probability of we coming at that node is a / n.
Now, the probability of arriving at the left subtree of that node is the probability of arriving at the node multiplied by the probability of choosing the left subtree.
So, the probability of arriving at the left subtree:
= a / n * b / a = b / n
Similarly, the probability of arriving at the right subtree:
= a / n * c / a = c / n
So, if the arrival process at some node is random, the arriving process is random on its children too. At the root node, the arrival probability according to our formula is n / n = 1. As we always start from the root node, the process satisfied the calculated probability.
Hence, it is proved that the arrival process is random.
Now, let’s prove that the selection process is random.
As the arrival process is random, the probability of arrival at some node is:
no of nodes in the subtree / total number of nodes in the tree (n)
Now, the probability of the node being selected is:
= probability of arrival at that node * probability of selecting that node = no of nodes in the subtree / n * 1 / no of nodes in the subtree = 1 / n
As the probability of selection of any node is 1 / n, the selection process is random.
Proved.
I remember a quote from Nelson Mandela, “It always seems impossible until it is done” and think about the algorithmic/mathematical puzzles. There are a number of mathematical/algorithmic puzzles that have taken decades to get solved. Some are still to be solved and many smart minds are burning the midnight oil to solve them.
For example, you can find “Millennium Problems” posted by Clay Institute which have one million USD cash prize for the solutions. Once a problem is solved, the solution is studied by many other researchers, scientists, and engineers. The solution is refined, optimized and studied more by other researchers and scientists. The solution is used as far as practicable by engineers in as many applications.
What do the problem-solvers see in the problems, solutions, proofs, optimizations, and implementations whether they are researchers, scientists or engineers? — Beauty. And it starts with some small problem, small algorithm, small proof. If you found this or any other algorithm beautiful, comment here. I would love to know which algorithm’s beauty are you most fascinated by.