Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
801
questions
0
votes
1
answer
26
views
BSTs with repeating keys
The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4.
We could try an ...
0
votes
0
answers
29
views
Finding the diameter of a N-ary tree graph, without using BFS
As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.
This must be done in linear time.
The problem states that the graph is undirected ...
- 109
5
votes
1
answer
102
views
Equivallent characterization of trees?
I am a teacher of undergrad graph theory and we tend to invent some weird (and false) characterizations of trees and recently I stumbled upon this one.
Is the following true?
$G$ is a tree if and only ...
- 221
0
votes
0
answers
19
views
How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?
Take this trie as example:
I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
- 1
1
vote
2
answers
78
views
Can two different binary trees can have identical post-order sequence
I have found that when drawing two trees having different structures, we can get the same in-order sequence and pre-order sequence. But I haven't found if two different binary trees can have an ...
- 11
0
votes
0
answers
14
views
How to prune a tree of selective nodes without recursion, using a stack [duplicate]
I can't solve the following problem without recursion. I get that the solution has to do with making a list of nodes to process but that's where I get stuck.
The problem is to remove all nodes from a ...
- 101
0
votes
0
answers
11
views
MIller and Reif's parallel tree contraction, are there any tutorials?
https://www.semanticscholar.org/paper/Parallel-Tree-Contraction-Part-1%3A-Fundamentals-Miller-Reif/7f9ac05b36277bae23de509090b2a3d27e9fd145
I am watching a lecture on this and it's a bit over my head ...
- 207
0
votes
1
answer
30
views
Node weighted Steiner Tree Problem where all Nodes have the same Weight
The node weighted Steiner Tree Problem as found in this compendium:
$\textbf{Instance}: \text{Graph } G = (V, E)\text{, set of terminals } S \subseteq V \text{ and a node weight function } w:V \to \...
- 103
0
votes
1
answer
32
views
All the keys in a binary search tree should be greater than or equal to the root of the tree, is my understanding correct?
A post claims 5 of the trees shown in the following figure are all binary search trees
I guess the author's making a mistake, since the 2 trees on the right ARE NOT binary search trees.
As an example,...
- 578
0
votes
0
answers
22
views
Time complexity of Trie autocompletion (multiple variables in time complexity)
I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
- 1
0
votes
2
answers
125
views
Best data structures to store overlapping intervals?
I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand.
Sample Input-1:
...
1
vote
2
answers
90
views
How to deal with a very big hash table?
I'm building an implementation of the dynamo paper, yottastore. Given a key, I need to find which NVMe block stores the data. To do that I hash the key to find the shard where I have an in memory ...
- 113
1
vote
1
answer
38
views
Why is calling an O(n) time algorithm on each node of a tree O(nlogn) time?
Assume we have a balanced binary tree.
On each node, we call:
...
- 143
1
vote
0
answers
36
views
Algorithm to recreate a Splay tree
Let's say I have some splay tree as following:
I want to recrate the exact same Splay tree using insert(key) method. Is there an algorithm that given some Splay ...
- 231
0
votes
0
answers
16
views
What is the depth of the tree after two operations if the tree uses the "Splay" heuristics?
Further to my previous question, I'm now trying to solve the same question but when the Splay action is involved:
It is given that the current tree is a string of $n$ vertices, and a search operation ...
- 231
0
votes
0
answers
25
views
What is the depth of the tree after two operations if the tree uses the "Move to Root" heuristics?
I'm preparing for my finals in "Advance Algorithms". I'm trying to solve the following question:
It is given that the current tree is a string of $n$ vertices, and a search operation is ...
- 231
0
votes
0
answers
14
views
Determine if a tree is connected from top to bottom
Consider the following scenario: you have a "tree", and it got many levels, each fill with nodes. nodes could only connect to other nodes that is one level above or below it. the connection ...
2
votes
0
answers
82
views
Is there a way to parallelise find and inserts for a binary search tree?
Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism.
I have implemented a ...
- 129
1
vote
1
answer
60
views
The relationship between a perfect binary tree and a complete & full binary tree
I am reading the book "Cracking the coding interview". In Chapter 4 they cover basic tree concepts.
It says there that a complete binary tree is a binary tree in which every level of the ...
- 113
0
votes
1
answer
24
views
Why are nodes added from left to right in last level in a Heap?
I understand that in Heaps we add them from left to right. I understand how to add and delete. But why is it from left to right, is there something that prevents it from being right to left or ...
0
votes
1
answer
44
views
Combinatorics under constraints
I have two sets of points in space with known positions:
$$A = \{r_1^{\alpha}, r_2^{\alpha}, ..., r_n^{\alpha}\} \quad n \in \mathbb{N}, \quad r_i^{\alpha} \in \mathbb{R^3}$$
$$B = \{r_1^{\beta}, r_2^{...
- 61
1
vote
1
answer
55
views
Calculating number of inversions in array using AVL Finger Tree
Problem: Let $ A $ be an array of $ n $ different elements from an ordered interval.
Let $ I(A) $ be the number of inversions in array $A$, meaning, the number of pairs of indexes $ 0 \leq i < j &...
- 233
3
votes
1
answer
89
views
Is possible to have a "pointer" to a tree node in a functional language?
Suppose I have the following structure definition in C:
struct node {
int value;
struct node *parent, *left, *right;
}
If I want to represent a specific ...
- 133
0
votes
0
answers
20
views
kth smallest in BST with updates
I am given a BST and have to find kth smallest element in which updates are also there. It means any value in tree can get updated and then I have to find kth smallest on updated tree. Some intuition/...
- 101
0
votes
0
answers
27
views
Worst Case for B Tree of order M with N Keys of Linear Search
Problem: Given a B tree with order M, having N keys, what is the total number of comparisons when applying a linear search.
Example: To perform a linear scan search for a single key on a set of one ...
- 1
5
votes
1
answer
125
views
Is there a solution to the following thought experiment / problem involving trees?
I am trying to find an algorithmic solution to a thought experiment that occurred to me recently. Please excuse me if the question is a bit naïve as I am not a CS expert.
Basically I have a tree with ...
- 1,110
3
votes
0
answers
33
views
Add an edge to a planar graph and preserving the planarity
I've already posted in the Math StackExchange section, but nobody answered.
I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if adding the ...
- 131
1
vote
1
answer
33
views
Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B
I've been given the question in the title:
Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in ...
- 11
0
votes
1
answer
80
views
I think I have discovered a new sorting algorithm using binary search tree [closed]
If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
0
votes
0
answers
36
views
Special case of single vehicle routing
I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
- 2,901
0
votes
0
answers
36
views
Using an undirected graph to represent an ordered pair?
Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
- 175
2
votes
1
answer
84
views
Proving that the number of leaves in a tree >= number of unmatched vertices
Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every ...
- 379
2
votes
2
answers
621
views
An α-good tree with n nodes has height O(log n)
Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by
$|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We
...
- 379
2
votes
2
answers
251
views
Decision tree for searching element in sorted-array
Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?
The answer is $ \Omega(\log n) $ ...
- 233
1
vote
1
answer
153
views
Find a path with given weight and the minimum number of edges on a tree
Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ ...
- 1
2
votes
1
answer
67
views
Bounding the height of a tree in a variant of disjoint set union
Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell_i$ = $⌊\log_2|T_i|⌋$ and, when merging $T_i$ ...
- 379
0
votes
0
answers
28
views
Algorithm for tracking the movement of nodes in a directed adjacency list
I have a directed adjacency list of node's. The structure of a node is
Node {
id: integer;
order: integer;
parentId: integer | null;
}
and the following ...
- 101
1
vote
1
answer
55
views
prove an inequality on binary tree
Let $\mathcal{T}_n$ be the set of ordered binary trees that have n leaves.
$d_T(v)$ means the node $v$'s depth in the tree T.
Prove: for any $T\in \mathcal{T}_n$ , for any $\{c_1,c_2,...c_n\}$ , $c_i &...
- 163
0
votes
2
answers
65
views
Find the largest MinHeap subtree in a given Tree
We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in ...
- 21
2
votes
0
answers
50
views
In a relaxed radix balanced (RRB) tree, how is the height determined in practice?
In a traditional radix-balanced tree, the height of the tree can be determined quickly by counting the leading zeros of the number of elements of the tree, and indexes to node children can be ...
- 121
2
votes
2
answers
97
views
How are a graph and a binary tree represented as data structures in CLRS' Introduction to Algorithms?
In CLRS' Introduction to Algorithms:
(1) In 22.1 Representations of graphs
The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V.
For ...
- 1
0
votes
0
answers
70
views
Is this greedy algorithm optimal?
Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$.
...
- 13
1
vote
2
answers
107
views
Find the spanning tree minimizing the backtracking in an unweighted graph
I am working with undirected unweighted graphs, and I am searching for an algorithm that gives me a spanning tree minimizing the number of moves to visit every nodes.
For example, given this graph :
...
- 121
1
vote
0
answers
20
views
Counting number of copies of a given tree T in a graph G. Looking for a randomised algorithm which is an FPRAS
I'm looking for a randomised algorithm (specifically an epsilon-delta approximation) which takes as input a graph G, a subgraph T (which is a tree), and outputs an approximation to the total number of ...
1
vote
1
answer
37
views
Why does this example of a Canonical Interval Decomposition contain keys and leaves that are outside of the interval?
I am reading Advanced Data Structures by Peter Brass for self-study, and was confused about the book's example of a Canonical Interval Decomposition for the Segment Tree section (section 4.2):
So, ...
9
votes
0
answers
187
views
Complexity of frog game on graphs is exponential, or can we do better?
Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
- 105
3
votes
1
answer
152
views
finding an algorithm for creating a priority search tree in linear time with presorting
A priority search tree is a binary tree satisfying the following:
every node $u$ stores a point $p_u = (x_u,y_u)$
every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate.
If $...
- 1
2
votes
1
answer
71
views
(Algorithm required) How to determine if a point is in one of many rectangles
What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it)
Whats the most ...
- 23
1
vote
2
answers
47
views
Space-efficient way to prove that a data has been processed before
Suppose that I have a stream of data packets in the form of unsigned 64 bit integers.
And I want to make sure that I am not processing the same packet content more than once.
A way of doing this would ...
- 11
1
vote
0
answers
15
views
How exactly are non-leaves in Monte Carlo tree search chosen?
I play around with Monte Carlo tree search and tic-tac-toe. For now I have followed the Wikipedia article. There is one place, where I am stuck, the selection phase. The given procedure is the ...
- 171