# Questions tagged [trees]

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

565 questions
Filter by
Sorted by
Tagged with
439 views

### Edge traversals of trees [closed]

I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of ...
133 views

12k views

### Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
2k views

### Priority queue with unique elements and sublinear time merge?

Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time. I am looking for a priority queue that merges in (expected|average|...
447 views

### Algorithm to determine if recursion was breadth first or depth first

Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have ...
4k views

### Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it? Background: Let the balance factor ...
76 views

### Numbering of unlabelled trees

For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?
1k views

### Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
263 views

### Find equidistant triplets in a tree

Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
688 views

### Number of Independent Sets in a tree

(I've been stuck on this homework assignment for far too long) I need to find the number of independent sets in a tree. For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are ...
689 views

### Why the height of the weight balanced tree is logarithmic

Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?
2k views

### Explanation of Heavy light decomposition

Can anyone explain heavy light decomposition of trees or give a resource to read it from? I have already gone through http://ipsc.ksp.sk/2009/real/solutions/l.html which is the best i could find but ...
72 views

### Which component sizes do we observe while randomly deconstructing a tree?

Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
3k views

### How to query and update ranges of arrays?

I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array. Decrease elements in range $[L,R]$ by $X$. Count the number of negative elements in range $[L,R]$. ...
379 views

### Queries on Tree

We have a tree with $N$ nodes. $N \le 10^5.$ Each node has a value $V$ associated with it. Now we have $Q$ $(\le 10^5)$ queries. There are two types of queries: Q X Y: in this type of query we have ...
261 views

### Origins of the Segment tree data structure

I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times ...
1k views

### Constructing Tree (forest) from Ancestor function

Question: Suppose I have a set of male people, and a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) ...
522 views

### How does insertion work in an AVL tree?

From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, feel ...
249 views

### Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing

I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is ...
90 views

### Assigning a formula to an approximate value

Let's say I have a software that calculates integrals, formally if possible and if not, then it computes an approximation by taking a small $dt$. Of course if the integral is an unknown number, I ...
2k views

### Find the number of topological sorts in a tree

Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself. I've tried thinking what would be the best for m to define it but couldn't get ...
62 views

### Nash Equilibrium in Tree of Bounded Degree

I have an exercise which I can't solve. Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
703 views

### Trouble understanding this dynamic programming solution

Here is the question: I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K. for ...
2k views

### Proving that the largest number of leaves in an $n$-ary tree of height $k$ is $k^n$

How to prove that the largest number of leaves in an $n$-tree of height $k$ is $k^n$?
10k views

### Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover). For each ...
169 views

### What makes Bayesian Networks decomposable into joint trees?

Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$. ...
437 views

### Euclidean Steiner Tree Question in Approximation Algorithms

Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$. ...
5k views

### How to generate uniformly random binary trees?

Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?
101 views

### Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$

Given we change the rule to: $-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$ I was wandering whether it's possible and how would it affect the trees' height, would it ...
45k views

### Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
2k views

### Given a tree, find a vertex which maximizes the minimum distance to any leaf

If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf. I am sure this problem has been studied before. Does anybody know the ...
981 views