# Questions tagged [trees]

Questions about a special kind of graphs, namely connected and cycle-free ones.

788 questions
Filter by
Sorted by
Tagged with
8 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 ...
• 101
17 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
21 views

### Best Case of Red Black Tree Insertion and Deletion

Question: During the insertion and deletion operation of a Red Black Tree data structure, each operation, can result in $\Omega(\log{n})$ color inversions? True or False? EDIT: Each operation ...
20 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 ...
122 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,100
30 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
30 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 ...
79 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 ...
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,871
25 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
81 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 ...
• 369
613 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 ...
• 369
107 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)$ ...
• 221
1 vote
137 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$ ...
55 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$ ...
• 369
27 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
42 views

56 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 ...
1 vote
46 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
14 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 ...
32 views

### What are other alternatives to version control on structured or large and highly volatile data?

Say you are editing a document like a 1000 page book. There are 20 authors all working furiously to edit the book. Every day they are merging their changes 2 or 3 times with the main branch. According ...
• 1,871
1 vote
108 views

I've faced this problem with my homework. We're given a weighted, undirected graph $G=(V,\ E,\ w)$ with weight function $w:E\rightarrow \mathbb{R_{\ge0}}$, someone deleted the weights of some edges $T\... • 456 1 vote 0 answers 31 views ### What are the interesting data structures to work with to manipulate mathematical expressions? For learning purposes only, I would like to make a small, fairly basic computer algebra system (CAS) manipulating mathematical expressions, such as polynomials, logarithmic or trigonometric ... • 255 1 vote 1 answer 59 views ### When is a max heap tree invariant under a root removal, followed by a re-insertion of the root? Let$T$be a max heap tree with no duplicate values amongst the nodes. When does$T$satisfy the following. Remove the root, and restructure the tree to satisfy the heap property. Reinsert the root, ... • 11 0 votes 2 answers 154 views ### Disjoint Set deletion The wikipedia entry for disjoint set data structure includes the statement (in the "Applications" section) Note that the implementation as disjoint-set forests does not allow the deletion ... 0 votes 0 answers 43 views ### Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching? In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ... • 1,871 0 votes 0 answers 30 views ### How to count the number of nodes for a tree generated by context free grammar derivation? Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language. For example: ... • 287 1 vote 1 answer 54 views ### If the distance to a vertex is updated in the n-th relaxation of Bellman Ford, is that vertex on a negative-weight cycle? Recently I asked a question Here about following topics: after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is ... 0 votes 0 answers 31 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 ... • 215 1 vote 1 answer 102 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 0 answers 30 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 ... • 456 0 votes 1 answer 87 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 ... • 215 0 votes 1 answer 81 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 ... • 456 0 votes 0 answers 38 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 1 answer 57 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 0 answers 33 views ### Data structure for quickly obtaining all axis-aligned rectangles completely within rectangular region I'm stuck on a homework assignment. There arenaxis aligned rectangles and we need to find a data structure of sizeO(n \log^2 n)$and query time$O(\log^3 n + k)$that can give all rectangles ... • 11 0 votes 0 answers 70 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? ... • 101 1 vote 1 answer 162 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 ... • 67 0 votes 0 answers 27 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 ... • 125 1 vote 1 answer 311 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 ...