# Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of $[1,N]$ each time, I send you the identifier of a node. when you receive a sent node. you mark it and also invoke the following marking rule, which takes effect before I send out next node.

• If a node and its sibling are marked, its parent is marked.
• If a node and its parent are marked, the other sibling is marked.

The marking rule is applied recursively as much as possible before the next node is sent.

Process 1 : each unit of time, I send the identifier of a node chosen independently and uniformly at random from all of the N nodes.

Process 2: each unit of time I send the identifier of a node chosen uniformly at random from those nodes that I have not yet sent.

Process 3: each unit of time I send the identifier of a node chosen uniformly from those nodes that you have not yet marked.

1. For the first process, prove that the expected number of nodes sent is $\Omega(N \log N)$
2. For the second process, you should find that almost all $N$ nodes must be sent before the tree is marked. Show that , with a constant probability, at leas $N - 2 \sqrt N$ nodes must be sent.
3. The behavior of the third process might seem a bit unusual. Explain it with a proof.

I need some hint how to proceed to analyze this process ??

• This seems to be a programming question and so out of scope here. – Yuval Filmus Jan 13 '15 at 22:39
• @YuvalFilmus I edited the question to suit this website. – Rathma Jan 14 '15 at 4:53
• @HadiAmiri But there's no question in your... question. – nouney Jan 14 '15 at 11:45