Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
571
questions
0
votes
0answers
13 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
44 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
25 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 ...
3
votes
1answer
39 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
38 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
17 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
17 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
14 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
16 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
21 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
0answers
21 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
51 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
10 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
47 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
46 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
9 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
61 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
168 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
3k 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
33 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
46 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
104 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
159 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
57 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
32 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
54 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
39 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 ...
1
vote
0answers
65 views
Tree Optimization, Combinatorics, algorithm [closed]
My Partners and me, we are trying to optimize frequency process...
I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java ...
1
vote
1answer
57 views
Minimum distance of nodes from a set of two nodes
In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
2
votes
1answer
102 views
Suggest a Data Structure To Manage 2 Sets
I was given the following problem which really baffled me, and I would like some guidance in solving it.
I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
0
votes
0answers
34 views
Algorithm to change order of tree
I'm looking for an algorithm name to change the order of the levels of a tree. I've done something that works but there's a lot of code and the $ O(n) $ is very bad.
Here's an example, let say there ...
1
vote
0answers
74 views
Find longest path in minimum spanning tree
Given an undirected MST with positive weights how can the longest path be found?
Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've ...
3
votes
0answers
83 views
How to cover holes with disks of a fixed radius? [closed]
So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These ...
1
vote
1answer
27 views
Merging and Unmerging Sets of Trees Efficiently
Background
Given multiple trees, I'd like to merge all of the them and be able to efficiently unmerge arbitrary trees in the set. For example, here are some JSON trees:
Tree 1:
...
3
votes
0answers
39 views
Tree Automata Operators
I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows:
...
3
votes
2answers
61 views
Minimally extend a tree such that there are no bridges in the new graph
We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph.
An edge $e$ is a bridge if the graph with that edge removed is no ...
0
votes
0answers
36 views
Real-world scenario for a theoretical problem on trees
Suppose one has a tree with each node weighted with a tuple (say, some fixed $2$ dimensions, for now) of integers. Now we query the tree with two vertices $x$ and $y$ and a range $[a,b]\times [c,d]$, ...
3
votes
1answer
65 views
Finding the shortest path for synchronized pawns in a maze
I have been trying to wrap my head around this problem, and I just can't get it.
We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
0
votes
1answer
25 views
Tree search returning parents and children
I've a flat structure where a node references its parent instead of children
class Node(int Id, Node Parent, string Data);
Given a list of all nodes, and a ...
3
votes
2answers
65 views
Size of tree decomposition
Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I ...
0
votes
0answers
23 views
Message Passing Algorithm and Implementation
I have a tree T with N nodes (Min-Span-Tree of a graph), and what I am gonna do is to calculate for each node Vi, the number of ...
0
votes
0answers
64 views
How to find the length of maximum subarray sum in segment tree query?
Problem: Given an array with size$\ n $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is ...
0
votes
0answers
38 views
Unite a forest if you know each tree's parent
I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively ...
1
vote
0answers
51 views
Given a tree find path that maximizes the median of the costs of edges
We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path ...
-1
votes
1answer
85 views
Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?
We are given a tree of N nodes from 1 to N where node 1 is the root of the tree.
For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
