Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 &...
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 $...
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 ...
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 ...

1
2 3 4 5
17