# Questions tagged [trees]

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

715 questions
Filter by
Sorted by
Tagged with
0answers
32 views

### How to reconstruct an existing splay tree by insertion?

I'm trying to figure out the same problem as stated in this question. In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
1answer
37 views

0answers
25 views

### Counting number of binary trees with given node values and root

I came across following problem: Find number of binary trees possible with 2 as roots. Nodes={1,2,3,4,5} There was no solution given. I knew number of binary trees for given preorder is given by ...
1answer
38 views

### Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$

I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement. I know it's a proof by induction and that the ...
1answer
536 views

### Determine minimum and maximum number of leaves on a complete tree

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$. I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
1answer
1k views

### Count total number of k length paths in a tree

This is a question from a competitive programming competition. Given a tree with n nodes and a number k, find the total number of paths of length k in that tree. I know for a fact that a solution can ...
2answers
396 views

### Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
1answer
40 views

### Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
0answers
335 views

### What's the number of leaves in AVL tree

How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree? I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
1answer
198 views

### Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?

I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed. The question is why is there the ...
1answer
848 views

### How to delete a node from BST tree with 2 chidren?

I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion ...
2answers
79 views

### Joining line segments to make tree

Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
0answers
62 views

### Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
1answer
55 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?
1answer
149 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.
0answers
67 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-...
0answers
203 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 ...
1answer
23 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'...
1answer
33 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 ...
2answers
2k 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 ...
1answer
489 views

### Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
1answer
132 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 ...
0answers
268 views

### Data structure for storing strings

I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) ...
1answer
340 views

### How to answer multiple queries for a tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each second, the ...