# Questions tagged [trees]

Questions about a special kind of graphs, namely connected and cycle-free ones.

586 questions
Filter by
Sorted by
Tagged with
22 views

### Prove G have a single MSP

We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?
65 views

### Enumerate all paths of length 3 in a given tree T

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.
17 views

### Counting nodes within K distance from set of given nodes in a tree [duplicate]

I was going through this article https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/ The question says: Given an undirected tree with some marked nodes and a positive ...
18 views

### Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
39 views

### Red-Black tree with index

I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index. So if I have the function: $\text{insert}(root, value, index)$ it will ...
20 views

### Finding most likely tree over a semilattice

If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees. Now assume that each semilattice edge is annotated with a transition probability. In addition, let'...
53 views

### Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

Here's the start and the vernacular I'm using. ...
117 views

### Solving $T(n) = T(n/2) + T (n/3) + n$ with recurrence tree

I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n$$ $$T(1) = Θ(1)$$ I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$ I ...
30 views

### Name for Turning DAG into redundant tree

I am looking for a term: How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
104 views

### Generate random labeled tree with constrained edge lengths

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes ...
46 views

### Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
38 views

### How to build tree from graph with specific property

We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written. We need to build tree such that for each node $i$, all nodes in the ...
3k views

135 views

### Merge Leaf labeled trees [closed]

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...