# Questions tagged [trees]

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

716 questions
Filter by
Sorted by
Tagged with
1answer
49 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, ...
1answer
47 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$ ...
1answer
154 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 ...
0answers
19 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 ...
2answers
85 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 ...
1answer
39 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 ...
1answer
43 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$...
1answer
35 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?
0answers
29 views

### What's wrong with this tree traversal algorithm?

I was asked to write a pseudo-code for iterative infix tree traversal. I came up with the following but I didn't get the marks. ...
0answers
30 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 ...
0answers
8 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 ...
0answers
31 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 ...
2answers
89 views

1answer
51 views

### MST and some facts via an example

$M$ is an MST of the Weighted Graph - $GR$. Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}. Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}. If $e$ is a edge ...
0answers
27 views

### data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations

I've got this question from an exercise and i'm not sure if it is possible to do so Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure ...
1answer
142 views

### Analysis of updating vertex and one example?

I see the following image on google: And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
0answers
15 views

### Fast but simple fully persistent trie

I need fast (not worse than about log of the sum of maximum number of nodes and the maximum number of subnodes per node) and fully persistent trie. I need an easy (quick to code) implementation. The ...
0answers
22 views

### Trying to convert algorithm from recursive to iterative

I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums: ...
0answers
46 views

0answers
9 views

### tool to insert nodes in a tree with queries

I have a tree where each node has a type. Multiple nodes can have the same type. I want to insert new nodes in this tree at some specific positions specified by queries, such as : ...