Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
716
questions
2
votes
1answer
49 views
A connected acyclic graph has $n-1$ edges
Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:
$G$ is connected
$G$ is acyclic
$G$ has $n-1$ edges
Proving $1, 2 \implies 3$
A connected, ...
1
vote
1answer
47 views
How can I make my algorithm more efficient?
I came across an algorithmic problem. I do not know how to do it optimally.
The problem is as follows:
There is an increasing array $A$ of size $n_1$
There is an array $M$ of queries of size $n_2$
...
4
votes
1answer
154 views
Changing a matrix to become an ancestry matrix
An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some ...
1
vote
0answers
19 views
Is there an official name for this tree merging algorithm?
Is there a standard name for an algorithm to handle this type of tree merge? Each node of the tree has a label. Nodes from the 2 trees should be combined if they have the same label, and their values ...
4
votes
2answers
85 views
Why does my code work: bijecting binary trees to Dyck paths
The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan ...
0
votes
1answer
39 views
How to calculate the average depth of a binary tree?
My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach ...
-1
votes
1answer
43 views
Time complexity of insertion in binary search tree
Given a binary search tree $T$, we insert $n$ elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$...
0
votes
1answer
35 views
Find successor element in heap
Does finding the successor of an element in a heap take $O(\log n)$?
An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?
-1
votes
0answers
29 views
What's wrong with this tree traversal algorithm?
I was asked to write a pseudo-code for iterative infix tree traversal.
I came up with the following but I didn't get the marks.
...
1
vote
0answers
30 views
Weight of lowest common ancestor satisfies strong triangle inequality
How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality:
$$ d(x,y) \le \max(d(x,z), d(y,z)) $$
How do I even start such a ...
0
votes
0answers
8 views
2D segment tree update/modification step complexity
I am having trouble understanding the complexity of the "Modification query" in https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/. It states at the bottom of the ...
1
vote
0answers
31 views
Count number of intervals containing a point
There is a problem (10.6) in Computational Geometry: Algorithms and Applications 2.edition by de Berg et al.
where you have to solve the problem of given $n$ intervals, $I$, on the real line, count ...
1
vote
2answers
89 views
Proving that a preorder traversal of a rooted tree can be performed in linear time
Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \...
1
vote
0answers
15 views
Better version of heavy-light decomposition: always draw path to largest subtree
Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ).
The problem: given any tree of size N, find a way to split it into ...
1
vote
0answers
18 views
Equally optimal nodes during minimax with alpha-beta pruning
Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (...
0
votes
1answer
46 views
AVL-tree insertion complexity proof
I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how.
I also tried to find it somewhere on the Internet, but I could not find any good results. Do you ...
1
vote
1answer
37 views
Relation between mathematical functions and trees?
I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me.
Is there a good way to model a tree in terms of functions?
1
vote
2answers
32 views
Efficiently enumerating all “good” strings given the ability to say whether a partial specification can be good
Suppose that I want to enumerate all English language words of length 5.
If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations.
...
1
vote
1answer
32 views
MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?
Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a ...
0
votes
0answers
18 views
How to find diffrenet ways to implement merge and delete_min operation in binomial heap?
I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says:
...
0
votes
1answer
41 views
2-3 tree: Sum of leaves in a given range
I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which ...
1
vote
1answer
50 views
What is the Number of epochs with no improvement after which training will be stopped.?
I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check ...
0
votes
1answer
37 views
How does CNN deal with rotation invariant pictures?
I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply ...
4
votes
2answers
67 views
How to make efficient path minimum queries in a tree?
Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them?
My ...
1
vote
1answer
28 views
minimum number of edges that should be added to an undirected graph to make it a tree
Basically, it's this rosalind problem.
You're given a number of nodes and an adjacency list.
My initial guess was that the answer was the number of connected components minus 1, since by joining every ...
0
votes
0answers
29 views
Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?
Given a binary search tree(can have any height) .Some nodes its value
changed and violate bst property how we can recover binary search
tree property in-place by just swapping a node with its ...
0
votes
1answer
49 views
Two definitions of Safe Edge
I ran into an interview two days ago and came across one strange definition of safe edge.
We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is ...
6
votes
1answer
177 views
Finding n farthest leaves in a tree
Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function:
$$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$
...
1
vote
1answer
48 views
Finding largest disjoint subtrees spanning nodes
I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found.
Now for each department, I would ...
1
vote
1answer
63 views
facts on tree and MST
We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.
The following ...
0
votes
1answer
23 views
How to (Efficiently) Sort a List of Items with Parent/Child Relationship
I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member ...
1
vote
2answers
42 views
How to index a tree to allow efficient search for paths?
By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be ...
0
votes
1answer
28 views
Height of a 2-3-4 tree
Consider the following 2-3-4 tree.
Does this have a height of 3 or 2 ?
If I count from the external nodes ie. the ones with the square boxes then height should be 3.
Not sure if they are to be ...
0
votes
1answer
40 views
How to prove that insert complexity in binary search tree is minimum O(log n)?
Is it connected to BST search O(log n) or height log n?
How to prove that insert will give give you correct BST in minimum O(log n) time?
1
vote
0answers
30 views
efficient DELETE in proto-Van Emde Boas Tree?
TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know ...
0
votes
0answers
27 views
Given two 2-3 trees I would like to merge them in $O(n_1+n_2)$
Given two 2-3 trees I would like to merge them in $O(n_1+n_2)$
I've solved before that if I get an ordered list then I can turn it into 2-3 tree in $O(n)$.
My questions is how can I turn two trees ...
2
votes
1answer
102 views
Number of nodes at given depth in binary tree
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction ...
0
votes
0answers
49 views
Creating Priority Search Tree bottom up from a Complete Binary Search tree in O(n)
I have a Complete Binary Search Tree of points ordered(sorted) on the y-axis (such that the point with the mid y of all the points is the root and its left children have decreasing y from the root and ...
0
votes
0answers
46 views
For every node of a tree, find the nearest ancestor node such that val[node] is coprime to val[ancestor]
Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note ...
1
vote
1answer
38 views
Should i work with tree representation as an array of nodes and an array of edges
Here is the problem, i have a graphical component that displays a tree. It takes as input an array of nodes and array of edges(eg:an edge has a source and target).
I will be performing complex tasks, ...
2
votes
1answer
176 views
Bellman Ford facts and specific question
The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following:
$d(v)>d(u)+w(u,v)$
holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)...
0
votes
1answer
51 views
MST and some facts via an example
$M$ is an MST of the Weighted Graph - $GR$.
Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}.
Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}.
If $e$ is a edge ...
0
votes
0answers
27 views
data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations
I've got this question from an exercise and i'm not sure if it is possible to do so
Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure ...
0
votes
1answer
142 views
Analysis of updating vertex and one example?
I see the following image on google:
And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
0
votes
0answers
15 views
Fast but simple fully persistent trie
I need fast (not worse than about log of the sum of maximum number of nodes and the maximum number of subnodes per node) and fully persistent trie.
I need an easy (quick to code) implementation.
The ...
0
votes
0answers
22 views
Trying to convert algorithm from recursive to iterative
I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums:
...
0
votes
0answers
46 views
Prove that $T(n)=\omega(n)$?
Edit: can someone provide clear answer with all details
Given:
$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$
I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
1
vote
0answers
28 views
Finding differences and similarities between tree graphs
Are there any known techniques for "diffing" trees, such as phylogenetic trees?
1
vote
1answer
57 views
How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$
I try to find tree height such that first i define:
$H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$
then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree ...
0
votes
0answers
9 views
tool to insert nodes in a tree with queries
I have a tree where each node has a type. Multiple nodes can have the same type.
I want to insert new nodes in this tree at some specific positions specified by queries,
such as :
...
