Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
677
questions
3
votes
1answer
32 views
BVH construction without sorting
Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives ...
0
votes
0answers
22 views
sum selected nodes of a set in $\log n$ time
Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation ...
4
votes
2answers
65 views
Can Edge Belong to a cycle if it is part of multiple BFS products
Given a simple connected undirected graph. with V vertices and E edges.
Let e be some edge from E.
If I perform |V| different BFS runs - meaning started each time from a different vertex - and in ...
0
votes
0answers
19 views
LOUDS Succinct Tree Representation
I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
0
votes
2answers
26 views
Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?
In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an
"Example of a heap storing 13 entries with integer keys. The last ...
2
votes
1answer
55 views
What does it mean that B-tree leaves carry no information?
According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.".
What does it mean that they carry no information?
...
0
votes
0answers
12 views
How do you prove that this tree path calculation function works, from first principles mathematically?
I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
0
votes
0answers
56 views
Are some algorithms inherently recursive?
Are some algorithms inherently recursive?
As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise.
I am asking because I struggled to ...
3
votes
1answer
110 views
How to detect “tree-able” set-families?
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
0
votes
1answer
28 views
Why does the formula floor((i-1)/2) find the parent node in a binary heap?
I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with
parent ...
0
votes
1answer
24 views
0
votes
0answers
14 views
How to convert recursive language grammar tree into automaton for optimal parsing?
So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees.
...
0
votes
1answer
26 views
What is a dominator node and a dominator tree?
I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node:
a node d dominates a node n if every path from the entry node to n
must go ...
0
votes
0answers
13 views
Derivation tree and Productions from left most derivation of string
How can one find Derivation tree and Productions of a Grammar from left-most derivation and string used?
I was given input string x = abaccacaa , left most derivation lder(x)=(1,2,1,3,4,1,3,5) and two ...
5
votes
2answers
139 views
Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
0
votes
1answer
47 views
Given two identical DOM trees find same node in tree B
So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'.
I can solve it in two ways -
Start at the given element and traverse up to ...
3
votes
0answers
56 views
Data structure to determine vertex membership after edge removal from a tree in sub-linear time?
Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$.
Is there a data structure that enables the immediate determination of ...
0
votes
1answer
25 views
Basic Binary search tree query
Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
1
vote
0answers
23 views
Recording a histogram in a tree exhibits strange best case
The task is to record a histogram from a streaming data source.
One data point is, say, a 16 bit integer. The maximum multiple of one data point before the stream ends, is < 2^32. The main ...
2
votes
0answers
65 views
Minimum number of nodes to select such that every node is at most k nodes away
I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck.
Given a binary tree where each node in the tree can either be selected
or unselected, ...
0
votes
0answers
22 views
What is the most efficient way to turn a list of directory path strings into a tree?
I'm trying to find out the most efficient way of turning a list of path strings into a hierarchical list of hash maps tree using these rules:
Node labels are delimited/split by '/'
Hash maps have the ...
1
vote
0answers
37 views
Number of ways to decompose a graph into two trees
Is there an efficient algorithm to count how many ways there are to decompose a given finite simple undirected connected graph $G = (V, E)$ into the union of two trees $T_1 = (V_1, E_1)$ and $T_2 = (...
3
votes
1answer
49 views
Merkle tree sorting leaves and pairs
I am implementing a Merkle tree and am considering using either of the two options.
The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input ...
-1
votes
1answer
43 views
How to answer the following queries on a tree?
Given a tree of "N" nodes(each node has been assigned a value A[i],node-"1" is the root of the tree), and a constant "K" , we have Q queries of the following type : [w]
(...
0
votes
0answers
14 views
Encoding a arbitrary stack trace into a fixed length value
Background
I would like to store the nodes of a Calling Context Tree using in a key value store. I need to be able to directly access a node by it's method name and complete stack trace. In addition ...
0
votes
1answer
24 views
Computing childrens of ith node of a d-ary tree
Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n).
The formula for indices of children of node no. i is given as:
{(1-i)d+2,
... , min{n,(1-i)d+d+1}...
2
votes
1answer
49 views
Runtime difference bewteen Union by Rank and Union by Size for union-find
I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)?
Intuitively,...
0
votes
0answers
40 views
Which advanced data structure to use?
For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
1
vote
1answer
60 views
Finding an MST with one adding and removing vertex operation
I am facing the following problem: Given an undirected complete Euclidean weighted graph $G(V, E)$ and its MST $T$. I need to remove an arbitrary vertex $v_i \in V(G)$, and given a vertex $v_j \notin ...
0
votes
1answer
85 views
Databases and B-Trees: What are Keys and how are they related
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for ...
1
vote
1answer
18 views
What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?
The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of ...
1
vote
1answer
179 views
Minimum cost of “signal” cover in a tree with DP
I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ ...
0
votes
1answer
42 views
Shortest path in BST
Given a Binary Search Tree and two elements $e1$ and $e2$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked ...
2
votes
1answer
51 views
Name of BFS variant with multiple queues with different priorities
Is there a name for the following variant of BFS that operates on trees with non-root starting point?:
Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
1
vote
1answer
35 views
Product of all nodes except for one in Binary Tree
Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...
2
votes
0answers
397 views
Facility location on a tree
Question:
Given a tree representing a neighbourhood where each node is a house.
Assign an antenna to each node such that the whole tree is covered.
An antenna of strength 0 can only ...
0
votes
0answers
25 views
Does this algorithm traverse trees in logspace?
Does this algorithm traverse trees (correctly) in logspace?
Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
1
vote
1answer
46 views
Can the structure of a “Complete Binary Tree”, be uniquely identified if only its pre-order or post-order or in-order traversals are given?
I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order.
The following is the definition of a complete ...
4
votes
1answer
50 views
Marginal Probability of Generating a Tree
Fix some finite graph $G = (V, E)$, and some vertex $x$.
Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows:
Let $T_0 = \{ x \}$.
For $0 < n \leqslant N$
i. Let ...
0
votes
1answer
46 views
Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?
I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree.
The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input ...
1
vote
0answers
64 views
Convert tree with recursive relationship to parent-child tree
Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good ...
0
votes
1answer
352 views
Find height of a ternary tree
Ternary heap is like a binary tree, just every node can have up to $3$ sons and not $2$.
I try to bound the number of nodes in the heap, $n$, using the height of the heap $h$.
The solutions get to:
...
0
votes
0answers
12 views
What is the insertion algorithm for an AVL tree with balance constraint of 2?
What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
0
votes
0answers
24 views
modifing CYK to compute the number of different parsing trees of a given sentence
Given a CFG in Chomsky Normal Form and a sentence s.
I want to count the number of different parsing trees that parses s.
assuming I know how to change the CYK algorithm so it would count the number ...
1
vote
0answers
65 views
Trees with duplicate nodes and path cancellations
I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
1
vote
1answer
18 views
Is there an Interval Tree which supports O(1) dynamic space requirements for queries?
I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).
In general ...
0
votes
1answer
25 views
Enhance B-Tree with find(k) function
I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
0
votes
0answers
8 views
Minimal t needed in B tree for the lowest reading time
I've got an assignment, which I was asked to calculate the minimal t needed in a B tree, to have the optimal searching time.
So here it is:
We've been told that in a specific B tree, with unknown t, ...
2
votes
2answers
72 views
Distance queries on Tree with hotspots
We are given a tree with $n$ vertices and some of the vertices act as a "hotspot".
We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest ...
1
vote
2answers
123 views
What's the name of this tree-like data structure?
I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties:
It consists of nodes and leaves
It has a single root element
Both nodes ...
