Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
741
questions
0
votes
0answers
20 views
Rebalance the following AVL tree after inserting G. You need to show the middle step if it happens. Briefly explain the operations
I recently learned AVL Trees but I still lack a complete understanding of the concept. I understand that an AVL tree is a Binary search tree that checks for the height of the tree, but I still don't ...
0
votes
0answers
26 views
How is red-black tree insertion more effective than avl tree insertion
I'm having trouble understanding why RB tree insertion is called more effective in all sources.
It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
2
votes
1answer
53 views
Why recording non-existent children in the pre-order traversal will differentiate different binary trees?
I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
-3
votes
1answer
119 views
Print all nodes which are the endpoint of the diameter of a tree
Given a tree with n nodes, Print all nodes which are the endpoint of the diameter.
1<= n <=100000.
E.g.
For Above tree answer would be A,B,F,G
I tried the O(n2) approach (Running Dfs from each ...
0
votes
0answers
26 views
Removing and adding edges from spanning tree
Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
0
votes
1answer
96 views
Time-varying edge cost Minimum Spaning Tree
I am having a hard time wrapping my head around the time-varying edge cost of this question :
Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
2
votes
0answers
27 views
Shortest path in a tree
Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
0
votes
1answer
26 views
What is the name of a sequence structure where writes in the same area are faster?
I recall reading about a data structure for sequences where writes in the same area are faster due to some kind of caching or structure manipulation. What are some structures that do this? I know a ...
0
votes
0answers
21 views
using TRIE for strings?
I saw the following question online:
Init - Initlize data structure in O(1).
Insert(s) - Add string s to your Data Structure in ...
0
votes
0answers
34 views
How to trasnform search tree into AVL tree with constant memory and in linear time? [closed]
How to transform search tree into AVL tree with constant memory and in linear time ?
0
votes
1answer
36 views
Query sum of values between lo and hi for a stream of numbers
Suppose you have a stream of incoming numbers that you're storing and at any given instant in time, you want to query the sum of values between a given lo and ...
2
votes
1answer
24 views
Building a game tree from a board game
Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
2
votes
1answer
48 views
Is this a valid encoding of a tree structure using set theory and a valid way to extract the leaves from it?
I'm looking to formally define a tree and then extract the leaves from it in a concise way.
Does this look ok?
What is the best way of doing this?
$
Y = \{a,b,c,d,e,f,g\} \\
R = \{a \mapsto b, a \...
1
vote
0answers
25 views
Minimal description for tree selection
If you have a tree, where nodes can be either selected or not selected, and you wanted to describe which nodes were selected or not you could either
List all the selected nodes and infer the others ...
1
vote
1answer
38 views
Applications of Complete Binary Tree?
Wondering what are the real word applications of the Complete binary trees or Almost complete binary trees where the the last level of the tree may not be complete and all nodes in the last level are ...
0
votes
0answers
20 views
What is the time complexity of comparing two Merkle trees?
I have a simple recursive function that compares two merkle trees and accumulates the differences in the leaf nodes. However, I am unable to measure the time complexity of it. Specifically, I would ...
0
votes
0answers
12 views
Generic real-time message/event matching engine
I'm looking for methods (any kind of combinations of algorithms & corresponding data structures) that can be used as a generic matching engine in case of arbitrary message/event types. Let me ...
0
votes
0answers
10 views
Full analyses of the number of nodes/keys and height of B-Trees
If I'm given a tree with "$k$" keys, or "$n$" nodes and I need to find the minimal / maximal height of the tree, I know that I have to split it into two cases:
$i$. The tree is ...
3
votes
1answer
46 views
Observations about the structure of an optimal Binary Search Tree
My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees.
I am confused about the following sentences:
Consider any subtree of a binary search tree. It must contain ...
2
votes
0answers
23 views
Minimum unrooted binary spanning tree
Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints:
tips have degree $1$
internal vertices ...
1
vote
1answer
49 views
More efficient way to parse array into binary search tree
Let's assume I have array which I need to parse into binary tree
...
0
votes
0answers
10 views
Dimensional reduction of quadtree influence on clustering with dbscan
Let's say we take a quadtree of 50 dimension and apply dimension reduction(Assume the dimension reduction works well). Why does the dimension reduction not influence the clustering with DBSCAN(Mintpts:...
0
votes
1answer
21 views
Children of internal node in a quadtree with high dimensionality
Let's say for example we have 1000 points and 50 dimensions.
And we build a quadtree where each node represents a 50-dimensional box and is divided by splitting the box into smaller boxes that are ...
-3
votes
1answer
150 views
If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x
Statement:
If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x.
Hint: Begin by computing a DFS tree, and prove an upper bound on its height.
I am supposed to prove the ...
4
votes
0answers
50 views
Collision detection with vary constraints
I have an edge-weighted tree, and for each leaf of the tree, there's a corresponding point on the 2D plane. For each pair of points $u$ and $v$, let $d_{uv}$ be the distance of the corresponding ...
2
votes
1answer
33 views
Optimal online algorithm to guess the tree
I have a tree on $n$ vertices. Your goal is to find the adjacency list for it.
$n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
0
votes
0answers
17 views
Partition in a tree shaped distributed network
We are given a synchronic undirected tree shaped network, with $n$ indexed nodes.
We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given.
We need to ...
0
votes
0answers
36 views
A claim regarding Huffman tree?
I saw the following claim:
Given $Q=\{1,2,\dots,n\}$ and $f$ (positive function) such that:
$$f(1)>f(2)>\dots>f(n)>f(1)/3$$
Then there are leafs at maximum 3 different levels of Huffman ...
3
votes
1answer
57 views
Algorithm to Compute High Water Mark
I saw this algorithm question which is as below.
There is a server that receives request Ids that are positive integers.
The High Water Mark (HWM) for the server at any instant of time is defined as ...
0
votes
0answers
14 views
Research on Tree Automata/Tree Transducers for implementing Tree Generators
I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically ...
0
votes
0answers
20 views
Alter Sankoff's Algorithm to give all optimal solutions
I'm trying to find a way to alter the Sankoff's Algorithm
so it will trace back all the optimal solutions and not only one.
Is it possible?
3
votes
1answer
85 views
Representing abstract syntax tree as a graph
Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code?
The goal and application ...
3
votes
2answers
190 views
Edge exchange property of two Minimum Spanning Trees
Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'
Then I want to prove ...
0
votes
1answer
49 views
Constructing a crown graph given an independent set
A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold:
(a) The set of neighbors of vertices in $C$ is ...
3
votes
1answer
42 views
Upper bound on the number of subgraphs in a tree
Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.
For example, consider the ...
1
vote
0answers
33 views
Why is converting a suffix tree to a suffix array not O(nklogk) time
Let's say that we have computed a suffix tree in O(n) time, and wish to use this to create a suffix array. According to wikipedia:
A suffix tree can be built in $O(n)$ and can be converted into a ...
0
votes
0answers
39 views
Augment the tree data structure for disjoint sets to implement the PRINT operation
Consider the following new operation for disjoint sets
PRINT(x): print every element in S_x the set containing x
One Approach that I found but couldn't figure out completely :
In addition to tree we ...
2
votes
1answer
146 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
48 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$
...
3
votes
1answer
164 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
20 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
118 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
125 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 ...
0
votes
1answer
78 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
133 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
vote
0answers
36 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
11 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
34 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
102 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
16 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 ...
