Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
598
questions
0
votes
1answer
31 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 ...
-3
votes
0answers
36 views
What are some generalizations of the tree diameter?
I am specifically interested in extensions and generalizations of the diameter concept on graphs. I can't find anything relevant in google scholar.
I have a certain result about tree diameters that ...
1
vote
1answer
41 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 ...
3
votes
2answers
108 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 ...
2
votes
1answer
28 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 ...
0
votes
0answers
19 views
Traversing/comparing tree structures with only parent references
Consider a tree structure with nodes containing references to only their parent. So, the root node's parent will be null. This tree represents a class hierarchy. The goal is to search such a tree for ...
2
votes
0answers
60 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)$ ...
1
vote
1answer
32 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 ...
0
votes
0answers
13 views
Does this kind of “conversation tree” has a specific name?
Does a Tree of infinite width and depth where each node represents a syntactically valid response to (a node of) a previous response to which it's connected via an edge has a specific name?
(It seems ...
0
votes
1answer
34 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 ...
3
votes
2answers
44 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 ...
3
votes
0answers
53 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 ...
1
vote
1answer
32 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?
0
votes
2answers
75 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.
0
votes
0answers
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 ...
1
vote
0answers
21 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-...
1
vote
0answers
44 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 ...
0
votes
1answer
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'...
0
votes
1answer
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 ...
1
vote
2answers
124 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 ...
1
vote
1answer
49 views
Which Tree traversal String is unique?
Assume we have a tree and we want to serialize it.
Example:
...
8
votes
1answer
105 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 ...
0
votes
0answers
23 views
how to construct a tree using root tree's code?
The Question is if we are given a binary code how construct a tree using that code? There was a question as follows:
By root tree's 000101001111 code, reconstruct that tree.
and the complete answer: ...
1
vote
0answers
129 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) ...
0
votes
1answer
126 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 ...
2
votes
0answers
104 views
How to query the 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 ...
0
votes
1answer
54 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.
...
0
votes
1answer
83 views
Leaf nodes of B+ Tree
I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
1
vote
1answer
32 views
Average number of full nodes in rooted m-ary tree
I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e.,
$$ \mu_{n}^{(m)} = \frac{\# \text{full nodes ...
0
votes
0answers
16 views
Traverse tree collecting nodes combinations
Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts.
Parts can be required - every build must contain them.
Parts can be optional.
Parts ...
0
votes
1answer
55 views
A* algorithm example explained
I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a ...
0
votes
0answers
28 views
How to find running time complexity of divide and conquer method without Master Theorem
I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
4
votes
1answer
48 views
How to find all the edges shared by all diametral paths of a tree?
A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are ...
2
votes
0answers
48 views
How to solve following tree problem?
Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very ...
0
votes
0answers
26 views
RB trees from any balanced BST?
Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be ...
0
votes
1answer
48 views
Merge nodes in a graph to form a tree
I have an undirected graph which may have 2 edges that connect the same pair of nodes.
A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a ...
0
votes
0answers
127 views
Maximum space consumption of stack and queue for DFS and BFS
I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS.
Since BFS and DFS while traveling graphs have ...
0
votes
0answers
29 views
Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general
A greedy algorithm for finding a minimum feedback vertex set
is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
0
votes
2answers
98 views
How to do a reverse topological sort using depth first search?
I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
0
votes
0answers
13 views
Efficiently calculate values based on subsets of a list
Let's say I have a list of items, each of which has some value
Eg. L1 = [A, B, C, ...]
And another list of items L2: [1, 2, 3, ...]. Each of the items in L2 needs to calculate the max value of a ...
0
votes
1answer
41 views
Disjoint Set Connected Components With Weighted Graph
I have been trying to solve this HackerRank problem (link).
The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
4
votes
1answer
161 views
Min Fibonacci Heap - increase key
I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
1
vote
0answers
14 views
Minimum Weight Binary Spanning Tree
Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every ...
1
vote
0answers
17 views
Directed Trees: Finding all the edges and vertices in a specific direction
I am an electrical engineer without experience in graph theory. However, I have a problem which I believe can be solved by graph theory. We have a directed tree, such as the one below. We want to find ...
0
votes
0answers
105 views
Minimum number of moves to reach a grid point by modified knight in variant chessboard
I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://...
0
votes
0answers
11 views
Depth of an R-tree, given $m$, $M$ and number of elements
Simply: what is the theoretical maximum, minimum or expected depth of an R-tree given $m$ minimum $M$ maximum elements in a node, with $N$ amount of nodes?
2
votes
1answer
81 views
How to merge a lot of trees into one single graph?
I have a few different trees, which resemble what the AST that compilers often deal with.
For example:
tree 1
( (a, b), (c, d) )
Imagine that each tree split represents the function "add", then ...
0
votes
0answers
11 views
Is Edmonds' Matroid partitioning algorithm optimal w.r.t lexicographical order?
We all know that, given a matroid $(E, \mathcal{I})$, Edmonds' Matroid partitioning algorithm will result in a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with optimal (...
3
votes
1answer
64 views
Algorithm to compute sum of cost of all path between pair of unique vertices of a tree
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.
Thus, there are total nC2 or n(n-1)/2 such ...
2
votes
1answer
169 views
Are all foldable data structures also recursive?
I was checking what Wikipedia has to say on reduce. It says:
In functional programming, fold (also termed reduce, accumulate,
aggregate, compress, or inject) refers to a family of higher-order
...
