Hot answers tagged

3 votes

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 ...
D.W.'s user avatar
  • 158k
3 votes
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 ...
Inuyasha Yagami's user avatar
2 votes

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 ...
Pål GD's user avatar
  • 15.8k
2 votes
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 ...
Discrete lizard's user avatar
  • 8,128
2 votes

Clarifications about tree-width definition

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....
Pål GD's user avatar
  • 15.8k
2 votes

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 ...
Steven's user avatar
  • 29.4k
2 votes
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 ...
Hendrik Jan's user avatar
  • 30.4k
2 votes

Recursive formula for height of BST

The formula is wrong. Indeed, we can find by hand that $H(1) = 0$, $H(2) = 1$ and $H(3) = \frac95$ ($5$ different trees, $4$ of them being of height $2$, the last of height $1$). But: $$\frac13\sum\...
Nathaniel's user avatar
  • 13.9k
2 votes
Accepted

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

The usage of "within" is a bit confusing, but I think it means the space complexity is never smaller than the time complexity divided by a factor of $b$. The space complexity of an algorithm ...
Discrete lizard's user avatar
  • 8,128
2 votes
Accepted

Does a sorted sequence from in-order traversal imply a binary tree is a BST?

Indeed. A binary tree is a BST iff its inorder traversal is sorted. First: when is a binary tree a binary search-tree (BST)? I for any node of the tree all nodes in its left subtree are less than the ...
Hendrik Jan's user avatar
  • 30.4k
1 vote

Parallel prefix sum/scan on trees

Here is one approach that ought to run fast on real hardware. Store the structure of your tree in an array $P$ so that the parent of node $i$ is found at $P[i]$. For example, with $$ P = [-1, 0, 0, 2, ...
Stand with Gaza's user avatar
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 ...
Nathaniel's user avatar
  • 13.9k
1 vote

Trying to implement BFS and I am stuck

The pseudo code for DFS using recursion would look something like this: ...
Amirreza Hashemi's user avatar
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 ...
Steven's user avatar
  • 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}$...
Inuyasha Yagami's user avatar
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.
Russel's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Discrete lizard's user avatar
  • 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 ...
NaturalLogZ's user avatar
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.
Edward Glukhov's user avatar
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 $...
Matt Timmermans's user avatar

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