2022 Developer Survey is open! Take survey.

New answers tagged

1 vote

Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B

Your idea to use a trie is good. I think that what might do the trick is only to store additionnal information at each node: the number of strings of $A$ and of $B$ contained in the corresponding ...
user avatar
  • 7,154
0 votes

Inorder Traversal of the Ternary Tree

A tree is a finite set of one or more nodes such that there is one specially designated node called the root node of the tree, and the remaining nodes are partitioned into trees $T_1,\ldots,T_k$ (...
user avatar
2 votes

I think I have discovered a new sorting algorithm using binary search tree

Nice work, but not useful because trees are not really sorted (in the sense of a sorted array) as the nodes may be stored non-contiguously in memory, and you need to follow the links; any BST is ...
user avatar
  • 3,337
2 votes
Accepted

Proving that the number of leaves in a tree >= number of unmatched vertices

Prove it by induction. It is true for trees with |V|<=3. Suppose that it is true for trees with |V|=n-1 and we want to prove it for a tree T with |V|=n. If there exist a leaf v which is unmatched ...
user avatar
5 votes

An α-good tree with n nodes has height O(log n)

First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| <\frac{1+\alpha}2 |x|$. Now consider $h_n$ the ...
user avatar
  • 7,154
6 votes
Accepted

An α-good tree with n nodes has height O(log n)

$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$ So, $|x| \ge \frac2{1+\alpha}|y|$. Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)...
user avatar
  • 33.1k
2 votes
Accepted

Decision tree for searching element in sorted-array

You haven't really defined your computation model, so here is a suggestion. The input to the algorithm is a sorted array $A$ of length $n$ and an element $x$. The output is either a position $i$ such ...
user avatar
0 votes

Decision tree for searching element in sorted-array

The lower bound can be found as the minimum height of a binary tree holding $n$ leaves. A complete tree has this property and has a logarithmic height.
user avatar
  • 3,337
2 votes
Accepted

Find a path with given weight and the minimum number of edges on a tree

This answer explains an algorithm that finds the minimum number of edges in $O(n\log n)$ time. With more bookkeeping, the path of weight $k$ with that minimum number of edges can also be found in $O(n\...
user avatar
  • 33.1k

Top 50 recent answers are included