Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
754
questions
0
votes
0answers
2 views
Upper bound of sum of sub-tree depth difference on a complete binary tree with $n$ leaves
A complete binary tree with $n$ leaves has $n-1$ internal nodes. For every internal node $i$, I care about the difference between the maximum depth of the left sub-tree and the maximum depth of the ...
0
votes
0answers
16 views
bellman ford and one surprizing fact
I ran into a very surprising local contest problem.
after finishing bellman ford algorithm, if we continue to updating
distance and distance of one vertex v being updated, then v is
on negative cycle....
0
votes
0answers
27 views
Find set of vertices of max size under some restrictions [duplicate]
I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question.
Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
0
votes
1answer
20 views
Bound the sum of leaf depth on a complete binary tree of $n$ leaves
A complete binary tree is defined as a tree where each node has either 2 or 0 children.
For a complete binary tree with $n$ leaves, there can be different arrangements of nodes, let's define the ...
0
votes
1answer
69 views
Find most vertices in a directed tree where no path of length less than 3 connects any pair
Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
0
votes
0answers
26 views
what should we add to a 2-3 tree to be able to find a value with this time complexity?
I've got this question that asks me to make changes to the 2-3 trees that would make it possible to do a find(x) function that would find x with O(log(rank(x))) .
**rank(x) is x's index in a sorted ...
4
votes
1answer
37 views
How can we process these types of queries on trees?
CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS
I recently thought of this interesting Tree problem:
Given a tree with $N$ nodes, let $val_i$ = the "value" for ...
1
vote
0answers
26 views
Data structure for quickly obtaining all axis-aligned rectangles completely within rectangular region
I'm stuck on a homework assignment. There are $n$ axis aligned rectangles and we need to find a data structure of size $O(n \log^2 n)$ and query time $O(\log^3 n + k)$ that can give all rectangles ...
0
votes
0answers
64 views
Efficient data structure supporting search query with contains
Suppose I have a table with millions strings in it as keys.
What data structure can I use in order to efficiently support only queries like that?
...
1
vote
1answer
155 views
Algorithmic Problem on Trees
Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...
0
votes
0answers
19 views
Treap use cases
I am trying to develop an appreciation for the treap data structure; my goal is not to implement one but use boost when the problem calls for this construct.
Some use cases, or small problems showing ...
0
votes
1answer
97 views
How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time
This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani.
Specifically, the problem statement is:
Give a linear-time algorithm that ...
0
votes
0answers
31 views
How do right contexts work in context-sensitive L-Systems?
I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
0
votes
1answer
56 views
How can it be proved that two different kinds of dfs unequivocally define a unique tree?
How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a ...
2
votes
1answer
80 views
Prove finding a spanning tree with no more than 50 leaves is NP-hard
This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard?
I think it is and I'm trying to ...
0
votes
3answers
47 views
How to make a Huffman tree
I'm trying to make a huffman tree based off of some words. I have the frequencies of each character stored using a hashtable, but i need to then make a minheap structure in order to then be able to ...
1
vote
0answers
27 views
Parse algebraic expression into a list of operations
Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as:
...
0
votes
1answer
111 views
AVL Tree rotations
What size is the largest AVL tree for which an insertion could trigger a double rotation?
0
votes
1answer
176 views
True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)
Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph.
True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
1
vote
1answer
40 views
m-ary tree relation between vertices and leaves
A full $m$-ary tree with $n$ vertices and $i$ internal vertices has $n = m \cdot i + 1$ vertices and
$l = (m − 1)i + 1$ leaves.
How can I prove it?
I know that $m$-ary tree is a rooted tree such that ...
0
votes
0answers
57 views
Write functions that run in O(1) time
This Question can be found in the book: ODS: An Introduction (Chapter 6)
Suppose we are given a binary tree with pre-, post-, and in-order numbers assigned to the nodes. Show how these numbers can be ...
0
votes
0answers
10 views
How does merkle trees help in effecient verification in a system like IPFS?
I do not understand how Merkle tree can be used to efficiently verify data in a peer to peer, distributed network like IPFS. I mean I understand how the merkle tree is constructed: basically take a ...
0
votes
0answers
38 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 ...
2
votes
0answers
40 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
69 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
1k 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 ...
1
vote
1answer
54 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
107 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
29 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
30 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
23 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
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
30 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
29 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
41 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
23 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
15 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
13 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
52 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
31 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
74 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
25 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
52 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
41 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 ...
3
votes
1answer
80 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
16 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 ...
