New answers tagged

0

It looks like the following set of four operations is sufficient. They are also minimal / necessary in the sense that no single operation can be removed from the set. right rotation at the root: . . / \ / \ . z => x . / \ / \ x y y z duplicating the tree deleting the left branch ...


1

Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y_{i-1},Y_{n-i}$ should be independent on $Z_{n,i}$. Here is what I got wrong: From $Y_n = \sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))$, I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z_{n,i}$ denotes ...


0

The idea is that the following two experiments produce the same random variable: A random permutation $\pi$ of $[n]$ subject to $\pi_i = n$. Choose a random subset $S$ of $[n-1]$ of size $i$, a random permutation $\alpha$ of $S$, a random permutation $\beta$ of $[n-1] \setminus S$, and let $\pi = \alpha, n, \beta$. The height of a BST based on the $\alpha$ ...


2

I'm assuming you have parent pointers, you can probably avoid them by maintaining a couple stacks though. Find the extremal two nodes $\ell \leq p \leq q \leq u$ and their common ancestor $a$ in $O(h)$ time. If nodes $p$ and $q$ are the same, return $S = \{p\}$. While $p$ is the left child of its parent and its parent is not the common ancestor, let $p := ...


1

Regarding your second question, yes two structurally different trees can have same inorder traversal. One such example is: A: B: 1 2 / \ \ 2 3 1 \ 3 Inorder traversal of both the trees is same. 2 -> 1 -> 3


Top 50 recent answers are included