Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
557
questions
0
votes
0answers
7 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?
1
vote
1answer
33 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
59 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 ...
0
votes
0answers
142 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
30 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?
...
1
vote
1answer
20 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
75 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
150 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
56 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
31 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
19 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
16 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
52 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
35 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
59 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
49 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
95 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 ...
0
votes
0answers
67 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
78 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
26 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
53 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
56 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 ...
2
votes
2answers
58 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
20 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
52 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
50 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
68 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 ...
3
votes
2answers
80 views
How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?
The recurrence I have is
$T(n) = 2T(\sqrt{n-1} + 2) + 1$
I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm ...
3
votes
1answer
47 views
Reversible Merge of Integer Hash Values
Context:
I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
2
votes
1answer
54 views
Time complexity of a tree-based algorithm
I solved a practice interview problem that was sent me by Daily Coding Problem mailing list. I am now curious about the exact time complexity of my solution.
Problem Statement
Given the mapping a =...
0
votes
2answers
142 views
prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves
I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction
*Edit: my professor had a significant typo in this assignment, I have attempted ...
1
vote
1answer
121 views
Is Breadth First Search Space Complexity on a Grid different?
Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:
For example, the flood fill question is described here:
https://www....
1
vote
1answer
35 views
Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert?
Im learning about tree data structures, and had a question that i couldnt find answer to so I came here.
Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it ...
1
vote
1answer
114 views
Tree traversal with conditional summing values from nodes
Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
1
vote
0answers
31 views
How do I implement fixed block storage file system in database from typical file-level file system?
I've a typical parent ID based file system in database and files are physically stored on disks. What I want is to store files in blocks (4096K) of fixed size.
Chunking can be used I found, but how ...
2
votes
0answers
100 views
Join Order Optimization
Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player
What is the optimal join order?
Based on the schema on the following picture:
I am suppoused (and that's what I tried) to use ...
1
vote
1answer
30 views
A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher
Referring to these notes regarding DFS - Click Here
They refer to the following claim that follows Definition 0.2. as observation:
A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and ...
1
vote
2answers
42 views
Term for the tree of all paths starting from a given vertex in a graph
What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?
This is the tree that is implicitly or explicitly constructed when ...
4
votes
2answers
569 views
Prove that the total distance is minimised (when travelling across the longest path)
Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have ...
1
vote
1answer
42 views
Rooted Tree Isomorphism Algorithm
I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:
Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$.
...
0
votes
0answers
27 views
How does a binary tree waste memory when stored as nodes and references?
I'm researching binary trees and came across this section describing storage methods.
It states that:
In a language with records and references, binary trees are typically constructed by having a ...
0
votes
0answers
106 views
How many maximum height AVL trees given height?
I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that ...
2
votes
0answers
26 views
Construct a lambda term from a Böhm tree
Given an acyclic graph, how can I build a lambda calculus term such that this graph is the term's Böhm tree?
If the Böhm tree is a finite tree (so the result is a strongly normalizing term).
If the ...
