# Tag Info

### Optimal graph data structure for set of points that allows dynamic updates

You are looking for a data structure for nearest neighbor search that supports dynamic updates. I suggest reviewing Wikipedia, as it has a good overview of many different data structures. Inserting ...
• 158k
Accepted

### Time complexity of tree algorithm

Note that the complexity of the algorithm depends on the tree $T$. For the maximally imbalanced tree, as you computed the complexity is $O(n^2)$. Another important observation is that the complexity ...
• 6,147

### Maximum Independent Set of a Tree using Greedy Algorithm

Yes, it would work for trees (acyclic graphs in general). You need to prove one thing. Let $\ell$ be a leaf in a tree. Then there exists a maximum independent set that contains $\ell$. The proof ...
• 15.8k
Accepted

### Does there always exist an optimal solution to the metric steiner tree problem which doesn't contain any steiner nodes?

No. The problem is that a single Steiner vertex can be involved in multiple of these shortcut operations. In the first shortcut operation, the total weight of the edges decreases (at the cost of ...
• 8,128

Yes, for a tree, the decomposition corresponds to one bag per edge. However, if you consider the graph $C_6$, the cycle on 6 vertices, you don't get a tree decomposition if you follow the same scheme....
• 15.8k

### Uniquness of a graph. Why do we need to add e1 to B to create a cycle?

If $e_2$ is the lightest edge from $B$ then the weight of $e_2$ could be smaller than the weight of $e_1$ (when $e_2$ also belongs to $A$). Even if such $e_2$ was in $B$ but not in $A$ and had a ...
• 29.4k
Accepted

### Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?

A binary tree is a binary search tree iff its inorder traversal yields an ordered list. Inorder (or symmetric) traversal is recursively defined as left-node-right. This recurrence is of course ...
• 30.4k

• 1,234
1 vote
Accepted

### Finding the pair of nodes with maximum distance in an arbitrary rooted tree

I don't know much about java, but there could be several ways to represent the tree: an array of $n$ adjacency lists, like an undirected graph; an array of $n$ integers, that contains the parent of ...
• 13.9k
1 vote

### Trying to implement BFS and I am stuck

The pseudo code for DFS using recursion would look something like this: ...
1 vote

### Finding a cycle of length log(n) given min degree

Assume that the graph is non-empty, pick an arbitrary vertex $s$ and construct the first $\lceil \log n \rceil$ levels of the BFS tree $T$ from $s$. You will encounter some non-tree edge $(u,v)$ in ...
• 29.4k
1 vote

### Minimum spanning tree with dynamic edge cost based on degrees

The Hamiltonian Path problem on undirected graphs can be reduced to your problem for $k = 2$ and $\beta \gg |V|$. Since the Hamiltonian Path problem is $\mathsf{NP}$-hard, your problem is $\mathsf{NP}$...
• 6,147
1 vote
Accepted

### Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes

You can check your reference, but every internal node (node with assigned key), with no internal child/children is by default has leaf node (NIL) as child/children.
• 2,735
1 vote

### What algorithm accepts a set of strings as input and outputs a regex of minimal size?

The minimal regular expression is [abcd...]*, where abcd... is the list of characters that appear in the input. This always ...
• 158k
1 vote

### find maximum in arbitrary expression tree

The general solution is to use symbolic execution. Let me start by explaining how to solve this if you have straight-line code, with no conditional statements (no if's). First, for each program ...
• 158k
1 vote

### Find the largest caterpillar subtree

I will show how to find the size of the largest caterpillar subtree, finding a caterpillar of that size can be done by keeping track of the decisions made in the formulas, similar to dynamic ...
• 8,128
1 vote

### Visualising pseudo-tree with two parents per node

In graph theory, a tree is is usually defined as a connected undirected graph with no cycles. One would also call a directed graph a tree if the underlying undirected graph is a tree. The concept of ...
• 541
1 vote

### Is every AVL tree a BST or just BT?

AVL is BST by definition of AVL. However, its self-balancing mechanism can be applied to any binary tree.
1 vote

### BIT: What is the intuition behind a binary indexed tree and how was it thought about?

I think that Fenwick trees/binary indexed trees are much easier to understand and prove if you don't think of them as trees at all. Partial Sum Array Given a subject array $A_0 ... A_{N-1}$ of length \$...

Only top scored, non community-wiki answers of a minimum length are eligible