Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
587
questions
3
votes
0answers
38 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
23 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
70 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
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-...
1
vote
0answers
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 ...
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
119 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
46 views
Which Tree traversal String is unique?
Assume we have a tree and we want to serialize it.
Example:
...
8
votes
1answer
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 ...
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
86 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
98 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
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.
...
0
votes
1answer
45 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
31 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
15 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
49 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
26 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
47 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
47 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
22 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
28 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
99 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
24 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
62 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
39 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
136 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
13 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
86 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
62 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
10 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
62 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
...
11
votes
4answers
4k views
Can the pre-order traversal of two different trees be the same even though they are different?
This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.
It is also mentioned that the in-order ...
2
votes
1answer
37 views
How to find size of each tree in a forest?
Let $T$ be a tree with $n$ nodes. If I remove $k$ edges from $T$, I will have $k+1$ new trees i.e. a forest of $k+1$ trees.
How do I calculate the number of nodes in each of these new trees formed?
...
3
votes
1answer
82 views
What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not
Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.
For example, consider the following two ...
0
votes
2answers
143 views
What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$
I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this ...
1
vote
1answer
182 views
how to find total paths in a graph which have only one vertex common with a given path
Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.
How can I find the total number of paths in the graph that do not share any edge ...
2
votes
1answer
64 views
Conditions for a binary tree being balanced
Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.
If you disprove, the counterexample should consist of an infinite ...
0
votes
1answer
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 ...
0
votes
0answers
21 views
What algorithms are there to build a junction tree of a graph?
A junction tree of a graph is a tree that represents the graph, so that certain information about the graph is encoded in the tree.
What algorithms are there to build a junction tree of a graph?
2
votes
0answers
18 views
Nested dissection vs kd-tree
Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
1
vote
1answer
56 views
Construction of a Deterministic Tree Automaton (DTA)
Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$.
We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t ...
1
vote
1answer
44 views
What are examples of applications of the tree decomposition of a graph? [closed]
I am looking for specific applications of the tree decomposition (of a graph), because I want to motivate its existence. What are examples of problems that are more easily solvable using the junction ...
