# Questions tagged [trees]

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

716 questions
Filter by
Sorted by
Tagged with
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, ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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$...
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?
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. ...
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 ...
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 ...
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 ...
89 views

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 ...
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 ...
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 ...
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 ...
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: ...