Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
671
questions
-2
votes
0answers
23 views
Are some algorithms inherently recursive “like”?
Are some algorithms inherently recursive "like" ?
As in, rewriting it in tail-recursive/iterative form a stack is still needed.
Struggled to implement ...
2
votes
1answer
101 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
20 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
17 views
0
votes
0answers
12 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
22 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
12 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
129 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
26 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
54 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
64 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
48 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
23 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
33 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
57 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
84 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
16 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
178 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
40 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
44 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
34 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
393 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
49 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
52 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
201 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
22 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
63 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
71 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
121 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 ...
1
vote
1answer
26 views
Understanding recursion tree for withdrawal formula
$$
T(n) = T(n-a) + T(a) + cn
$$
Now the solution says that the height of the tree $(h)$ is:
$$
h = \left \lfloor n/a \right \rfloor
$$
And I don't understand why. Maybe I didn't understand the ...
0
votes
0answers
17 views
How to reconstruct an existing splay tree by insertion?
I'm trying to figure out the same problem as stated in this question.
In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
1
vote
1answer
35 views
Why $T(n)=6T(n-1) + n^3$ has such a mess solution?
I tried to solve the recurrence relation
$T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^...
3
votes
0answers
45 views
Is there a *natural* problem that is NP-hard on trees, but in P on non-trees?
It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong?
Question: Is there some natural decision problem on ...
0
votes
1answer
28 views
Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$
I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it?
...
0
votes
0answers
31 views
creating a binomial heap with only pointer object references
I have a problem where I must make a binomial heap in Python. I have almost all of the methods working except for the bubbleUp method.
The problem I am having is ...
1
vote
2answers
155 views
Minimum-average-cost subtree that is not necessarily spanning
I'm looking for an efficient algorithm for the following problem:
Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root)....
