Suppose that we are dealing with a non-empty binary tree T, that satisfies the first two properties of a treap. Meaning that each node stores an ordered pair (e,p) where e $\in$ $\mathcal{E}$ and p $\in$ P. Along with this, the element at a root node x is greater than the element stored in the left subtree of this root x, but less than the element stored in the right subtree of this root x. We can also assume that a node x of a binary tree $\mathcal{T}$ is used as input. Then the first two preconditions of the “Treap Restoration after Deletion” problem are satisfied.

Suppose that x has a non-null child where the priority at the left child of x is greater than the priority stored at x. Along with this, the priority stored at the left child of x is greater than or equal to the priority of the right child of x, given that it is not null and actually exists.