Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
823
questions
0
votes
0
answers
48
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 ...
- 151
0
votes
1
answer
27
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
87
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
-3
votes
0
answers
41
views
In a tree structure, when we say the keys are only stored in leaves, what do we do with other nodes?
Consider the following question describing a custom tree data structure:
Consider a data structure D which stores a1, a2, ..., an in it's leaves. Also, the internal nodes store minimum value of their ...
0
votes
0
answers
48
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 ...
- 109
0
votes
1
answer
28
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 ...
- 176
2
votes
4
answers
117
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
28
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
120
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
25
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
1
vote
1
answer
75
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,...
- 88
0
votes
0
answers
34
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
28
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 ...
- 53
1
vote
1
answer
48
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 :...
- 117
0
votes
2
answers
63
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 ...
- 151
0
votes
2
answers
83
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
55
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
22
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
322
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
23
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
30
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 ...
- 141
0
votes
0
answers
27
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 ...
- 391
2
votes
0
answers
50
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
39
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
48
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 ...
- 306
5
votes
1
answer
107
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 ...
- 223
0
votes
0
answers
20
views
How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?
Take this trie as example:
I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
- 1
1
vote
2
answers
109
views
Can two different binary trees can have identical post-order sequence
I have found that when drawing two trees having different structures, we can get the same in-order sequence and pre-order sequence. But I haven't found if two different binary trees can have an ...
- 11
0
votes
0
answers
16
views
How to prune a tree of selective nodes without recursion, using a stack [duplicate]
I can't solve the following problem without recursion. I get that the solution has to do with making a list of nodes to process but that's where I get stuck.
The problem is to remove all nodes from a ...
- 101
0
votes
0
answers
15
views
MIller and Reif's parallel tree contraction, are there any tutorials?
https://www.semanticscholar.org/paper/Parallel-Tree-Contraction-Part-1%3A-Fundamentals-Miller-Reif/7f9ac05b36277bae23de509090b2a3d27e9fd145
I am watching a lecture on this and it's a bit over my head ...
- 207
0
votes
1
answer
42
views
Node weighted Steiner Tree Problem where all Nodes have the same Weight
The node weighted Steiner Tree Problem as found in this compendium:
$\textbf{Instance}: \text{Graph } G = (V, E)\text{, set of terminals } S \subseteq V \text{ and a node weight function } w:V \to \...
- 103
0
votes
1
answer
49
views
All the keys in a binary search tree should be greater than or equal to the root of the tree, is my understanding correct?
A post claims 5 of the trees shown in the following figure are all binary search trees
I guess the author's making a mistake, since the 2 trees on the right ARE NOT binary search trees.
As an example,...
- 578
0
votes
0
answers
45
views
Time complexity of Trie autocompletion (multiple variables in time complexity)
I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
- 1
0
votes
2
answers
204
views
Best data structures to store overlapping intervals?
I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand.
Sample Input-1:
...
1
vote
2
answers
125
views
How to deal with a very big hash table?
I'm building an implementation of the dynamo paper, yottastore. Given a key, I need to find which NVMe block stores the data. To do that I hash the key to find the shard where I have an in memory ...
- 113
1
vote
1
answer
59
views
Why is calling an O(n) time algorithm on each node of a tree O(nlogn) time?
Assume we have a balanced binary tree.
On each node, we call:
...
- 143
1
vote
0
answers
46
views
Algorithm to recreate a Splay tree
Let's say I have some splay tree as following:
I want to recrate the exact same Splay tree using insert(key) method. Is there an algorithm that given some Splay ...
- 223
0
votes
0
answers
21
views
What is the depth of the tree after two operations if the tree uses the "Splay" heuristics?
Further to my previous question, I'm now trying to solve the same question but when the Splay action is involved:
It is given that the current tree is a string of $n$ vertices, and a search operation ...
- 223
0
votes
0
answers
27
views
What is the depth of the tree after two operations if the tree uses the "Move to Root" heuristics?
I'm preparing for my finals in "Advance Algorithms". I'm trying to solve the following question:
It is given that the current tree is a string of $n$ vertices, and a search operation is ...
- 223
0
votes
0
answers
17
views
Determine if a tree is connected from top to bottom
Consider the following scenario: you have a "tree", and it got many levels, each fill with nodes. nodes could only connect to other nodes that is one level above or below it. the connection ...
2
votes
0
answers
117
views
Is there a way to parallelise find and inserts for a binary search tree?
Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism.
I have implemented a ...
- 129
1
vote
1
answer
80
views
The relationship between a perfect binary tree and a complete & full binary tree
I am reading the book "Cracking the coding interview". In Chapter 4 they cover basic tree concepts.
It says there that a complete binary tree is a binary tree in which every level of the ...
- 113
0
votes
1
answer
29
views
Why are nodes added from left to right in last level in a Heap?
I understand that in Heaps we add them from left to right. I understand how to add and delete. But why is it from left to right, is there something that prevents it from being right to left or ...
0
votes
1
answer
44
views
Combinatorics under constraints
I have two sets of points in space with known positions:
$$A = \{r_1^{\alpha}, r_2^{\alpha}, ..., r_n^{\alpha}\} \quad n \in \mathbb{N}, \quad r_i^{\alpha} \in \mathbb{R^3}$$
$$B = \{r_1^{\beta}, r_2^{...
- 61
1
vote
1
answer
62
views
Calculating number of inversions in array using AVL Finger Tree
Problem: Let $ A $ be an array of $ n $ different elements from an ordered interval.
Let $ I(A) $ be the number of inversions in array $A$, meaning, the number of pairs of indexes $ 0 \leq i < j &...
- 233
3
votes
1
answer
105
views
Is possible to have a "pointer" to a tree node in a functional language?
Suppose I have the following structure definition in C:
struct node {
int value;
struct node *parent, *left, *right;
}
If I want to represent a specific ...
- 133
0
votes
0
answers
22
views
kth smallest in BST with updates
I am given a BST and have to find kth smallest element in which updates are also there. It means any value in tree can get updated and then I have to find kth smallest on updated tree. Some intuition/...
- 101
0
votes
0
answers
34
views
Worst Case for B Tree of order M with N Keys of Linear Search
Problem: Given a B tree with order M, having N keys, what is the total number of comparisons when applying a linear search.
Example: To perform a linear scan search for a single key on a set of one ...
- 1
5
votes
1
answer
126
views
Is there a solution to the following thought experiment / problem involving trees?
I am trying to find an algorithmic solution to a thought experiment that occurred to me recently. Please excuse me if the question is a bit naïve as I am not a CS expert.
Basically I have a tree with ...
- 1,100
3
votes
0
answers
35
views
Add an edge to a planar graph and preserving the planarity
I've already posted in the Math StackExchange section, but nobody answered.
I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if adding the ...
- 131