2
$x_1=5, x_2=7$ is the smallest example where there is no common ancestor. Any ancestor of $x_1$ is in the range $2 \cdot 2^k + 1 \le z \le 3 \cdot 2^k - 1$, any ancestor of $x_2$ is in the range $3 \cdot 2^k + 1 \le z\le 4 \cdot 2^k - 1$. These are non-overlapping intervals with a gap of one number in between.
1
The reason you give is not exactly right; the definition of a dominator node works from a starting node ($1$ in the example). The only way to reach $3$ from $1$ is to go through $2$ as it is the sole successor node of $1$ in the given graph. Hence $2$ dominates $3$. For the same reason, the nodes $4$ through $6$ are also dominated by $2$ and further, $2$ is ...
1
If the height is $0$ it is true.
Assume that all binary trees for which inorder is sorted and height smaller than $h$ are BST.
Consider a tree with root $x$, height $h$ and its inorder is sorted. In particular its left and right subtrees' inorder are sorted and have height smaller than $h$. Then, by the assumption, they are BST. Now, in the inorder of the ...
Only top voted, non community-wiki answers of a minimum length are eligible
