Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
839
questions
0
votes
0
answers
21
views
Mapping relationtional data to hierarchical data (JSON, XML, etc.)
I'm working on a project that involves mapping relational data to a tree hierarchy. The hierarchical data is preferred to be JSON or XML. Is there an existing general algorithm for this?
Current ...
0
votes
0
answers
31
views
Dynamic Program to find well formed set in a rooted tree
You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
- 139
0
votes
0
answers
9
views
Morton-code based Linear BVH: Why do triangle's bounding boxes' centroids give higher-quality trees than triangles' centroids?
I've implemented linear BVH as described in Karras 2012, and I was using triangles' centroids for Morton Code generation. I found recent papers and implementations use triangles' bounding boxes' ...
1
vote
2
answers
88
views
NP-hardness of modified distance-colouring of graphs
Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
- 11
0
votes
2
answers
41
views
Trying to implement BFS and I am stuck
I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue.
On the one ...
0
votes
0
answers
61
views
Finding the Depth-First Index of a Child Given the Parent's Depth First Index Index in Complete k-ary Tree
I have a complete k-ary tree with a depth of $d$. If I'm given a node's depth-first index, I'd like a closed-form formula for calculating both the nodes children's depth-first indexes along with a ...
- 101
1
vote
1
answer
41
views
Efficient intersection of multiple paths in a tree
Consider a graph tree $T$, where we are given $k > 1$ unique pairs of nodes $\{u_1,v_1\}\dots \{u_k,v_k\}$. Let $P_{i}$ denote the unique path on $T$ between $u_i$ and $v_i$. Then, my problem is ...
- 13
0
votes
1
answer
31
views
Uniquness of a graph. Why do we need to add e1 to B to create a cycle? [closed]
If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it'...
- 19
0
votes
1
answer
30
views
Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?
I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list.
The ...
- 105
0
votes
1
answer
226
views
Finding a cycle of length log(n) given min degree
Let $G = (V, E)$ be an undirected graph such that every $v\in V$ has $\deg(v) \geq 3$. We must create an algorithm that outputs a cycle of length O(log(n)) if it exists. This algorithm must return in ...
0
votes
0
answers
20
views
Subtrees of decision tree for comparison sort are recurrences?
Consider sorting on $n$ distinct elements, where all $n!$ permutations are possible. I think a decision tree for comparison sort can can be uniquely characterized as $T(a,n!)$ where $a$ is the ...
- 129
0
votes
0
answers
11
views
Keeping in a list a list of recent insertions/removal to/from a list of lists
I have a list of lists T.
I stress test my database software by randomly adding and removing sublists and elements of sublists to/from T and from/to my database. (After this I compare T with the ...
- 433
0
votes
0
answers
33
views
Are pre-order, in-order and post-order the only traversals for depth-first search?
With a binary tree, the 3 approaches for the tree below are listed.
...
- 659
0
votes
0
answers
40
views
Is my mathematical representation of search in binary search tree correct?
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals <...
- 113
2
votes
0
answers
99
views
On definitions of graph width
Wikipedia shows graph width $k$ as the degeneracy, an ordering of the vertices $v_1,\ldots , v_k$ for which, if we orient each edge $(v_i, v_j)$ towards $i$ where $i<j$, the maximal degree is at ...
- 435
0
votes
2
answers
56
views
AVL tree with balance factor equal to depth
If you were to define an altered AVL tree where the balance factor (the difference between the height of the left and right subtree) of a node must be less than or equal to the depth of the node (in ...
- 3
1
vote
1
answer
61
views
Clarifications about tree-width definition
I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here:
https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb
I'm finding ...
5
votes
0
answers
75
views
Completeness of red-black tree operations
Red-black trees are defined to have the following invariants:
The nodes are in sorted order (it is a binary search tree).
The root is black, and leaves are black.
Every red node has black children.
...
- 531
0
votes
1
answer
75
views
BFS on a graph and BFS on a tree
I found the following question in my book and I have no clue on what the answer should be:
What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree generate ...
- 1
2
votes
1
answer
96
views
Minimum spanning tree with dynamic edge cost based on degrees
I have a problem that I'm struggling to solve or even name, I'd really appreciate any help or pointer to potential existing solutions.
Suppose there is a connected graph $G$ and we are trying to find ...
- 21
3
votes
1
answer
353
views
Maximum Independent Set of a Tree using Greedy Algorithm
I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?
...
- 31
0
votes
2
answers
49
views
Does there always exist an optimal solution to the metric steiner tree problem which doesn't contain any steiner nodes?
Given an undirected graph with nonnegative edge weights and a partition of the vertex
set into terminals and Steiner vertices, the Steniner tree problem consists in finding a
minimum weight tree in ...
- 423
0
votes
1
answer
156
views
Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes
To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children.
For the inductive step, consider a node $x$ that has positive height and is an ...
- 25
0
votes
1
answer
26
views
What algorithm accepts a set of strings as input and outputs a regex of minimal size?
We seek an algorithm.
Inputs to the algorithm are a set of strings $A$ and the output of the algorithm $A$ is a regular expression $r$ such that:
The size of regular expression $r$ is minimized.
If $...
0
votes
0
answers
63
views
What algorithm will convert a regex into a tree of predictable size?
How do we quantify the size of a regular expression?
A problem in computer science which sometimes arises is converting a regular expression into a tree.
What rules can we use to ensure that the tree ...
0
votes
0
answers
55
views
Is there a cannonical name for a tree in which none of the nodes have a value attribute except for the root node?
Is there a canonical name for a tree in which none of the nodes have an attribute to store a value, or data-item, except for the root node?
A primitive implementation of this data-structure is shown ...
0
votes
1
answer
34
views
find maximum in arbitrary expression tree
Originally posted on SO.
I have a very simple language that gets compiled to an Expression tree, and then evaluated. Users can define mathematical operations, use variables and control flow. Moreover, ...
- 101
3
votes
1
answer
111
views
Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...
Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
- 31
1
vote
1
answer
81
views
fastest algorithm to count leaf nodes (i.e. terminal nodes)
With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time?
Python code - (mag(P) = number of leaf nodes of tree ...
- 119
0
votes
1
answer
37
views
the size of nice tree decomposition
Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation.
For a ...
- 318
2
votes
4
answers
143
views
Best C++ STL container to store bodies in an N-body simulation?
I am writing an N-body simulation in C++ that has to be able to deal with large N ($N \le 10^6$).
Everything has been going well so far, but now that I have started to code in collisions between ...
0
votes
0
answers
88
views
Range updates in segment trees of sorted arrays (merge sort trees)
I understand range updates in segment trees using lazy propagation where each node is an integer.
Merge Sort Tree (source GFG): https://media.geeksforgeeks.org/wp-content/uploads/20220722205737/...
- 139
2
votes
1
answer
125
views
Is there a name for this kind of binary tree?
While working on a math problem the following tree structure came up:
o
\
o
/
o
/ \
o o
/ \ /
It is a binary tree with the ...
- 123
0
votes
0
answers
34
views
What type of tree traversal should be performed to obtain the same splay tree?
I'm trying to figure the following:
Given splay tree number 1. Perform a tree traversal on it and insert each node into splay tree number 2 in that order. What type of tree traversal should be ...
- 223
0
votes
1
answer
93
views
Set of all vertices in a directed tree that are within distance of strictly larger than 2
As the title says, I'm trying to solve the question where:
Input: A directed tree $T = (V, E)$.
Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u,...
- 11
0
votes
0
answers
40
views
How the depth of the vertices changes along the route in the splay tree after search
Studying for the exam in "Advanced Algorithms" course. I'm trying to solve the following question:
This question discusses a search operation for a vertex ...
- 223
1
vote
1
answer
30
views
Optimum placement of zigzag trees in order to minimize the makespan
Suppose we have some trees of the following forms:
We want to place these trees in a linear fashion in a way such that the last node has the minimum distance to the first node. For instance, if we ...
- 153
1
vote
1
answer
65
views
Generate uniform random vectors
Problem : Consider a random vector $v$ which is uniformly distributed over the sample space $S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$ . How to efficiently generate such random vector ?
note :...
- 129
0
votes
2
answers
103
views
How might we hash two trees?
Suppose that you had two trees.
Our goal is to convert the two trees into two integers such that two trees are the same if and only if the two integers are the same.
Suppose that we have a function ...
1
vote
2
answers
192
views
Why would we want to convert a forest or generic tree to binary tree?
Why sometimes we would want to convert generic trees or forests into a binary tree? And what's the main principle behind this convertion?
1
vote
0
answers
70
views
Find maximum number of vertex-disjoint paths of length $k$ in a tree with no restrictions for the paths
I am working currently on Path-Packing problems and found this Book:
https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
My question is about exercise 23b on page 184.
Here is ...
- 11
1
vote
1
answer
38
views
Visualising pseudo-tree with two parents per node
I have an algorithm that recursively connects together pairs of nodes into new nodes. It looks like the Huffman code algorithm, except that a node can be re-used after it has been part of a merge. The ...
- 141
2
votes
1
answer
471
views
Comparing two rooted n-ary trees irrespective of the order of children nodes?
I want to compare two trees:
I will consider the trees equal if they are:
Isomeric-i.e have the same structure.
Nodes in both trees have the same values but the order of the children nodes are not ...
- 65
1
vote
1
answer
38
views
Enumeration of tree vertices such that each vertex has unique neighbor appearing before it
(Diestel, Graph Theory) Corollary 1.5.2: Every tree has an enumeration of the vertices $\{v_1, v_2\ldots v_n\}$ such that each vertex $v_i$, with $i\geq 2$, has a unique neighbour in $\{v_1, v_2\...
0
votes
1
answer
48
views
Choosing root for maximum matching in tree
This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part.
Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
- 140
1
vote
1
answer
62
views
Showing that all gomory hu trees of $K_{3,3}$ are stars with 5 edges
My lecture notes for gomory-hu trees says that it's easy to see that every GHT of the utility graph $K_{3,3}$ is a star with 5 edges. Is there any easy way to see this without manually computing every ...
- 423
2
votes
0
answers
69
views
Questions about the Dancing Tree data structure
I would be very grateful if someone can clarify a little bit about the Dancing tree data structure that the Reiser4 filesystem uses. It's a presentation topic that I picked, however, there seems to be ...
0
votes
1
answer
50
views
BSTs with repeating keys
The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4.
We could try an ...
0
votes
0
answers
60
views
Finding the diameter of a N-ary tree graph, without using BFS
As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.
This must be done in linear time.
The problem states that the graph is undirected ...
- 315
5
votes
1
answer
111
views
Equivallent characterization of trees?
I am a teacher of undergrad graph theory and we tend to invent some weird (and false) characterizations of trees and recently I stumbled upon this one.
Is the following true?
$G$ is a tree if and only ...
- 267