Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [trees]

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

3
votes
2answers
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|...
3
votes
2answers
430 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 ...
2
votes
1answer
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 ...
3
votes
1answer
74 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?
38
votes
0answers
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 ...
4
votes
1answer
236 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 ...
2
votes
1answer
681 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 ...
0
votes
2answers
680 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?
5
votes
1answer
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 ...
2
votes
0answers
70 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 ...
4
votes
2answers
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]$. ...
2
votes
1answer
367 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 ...
5
votes
2answers
259 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 ...
3
votes
2answers
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) ...
2
votes
1answer
519 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 ...
7
votes
1answer
243 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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
672 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 ...
-3
votes
1answer
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$?
13
votes
2answers
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 ...
1
vote
1answer
168 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$. ...
2
votes
1answer
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$. ...
5
votes
1answer
4k views

How to generate uniformly random binary trees?

Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?
3
votes
1answer
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 ...
43
votes
3answers
44k 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'$. ...
7
votes
2answers
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 ...
5
votes
2answers
965 views

Which data structure to use to solve equations?

Let's say I have two equations for a geometric object (a rectangle): $\left\{ \begin{array}{l} x \ge 0 \\ y \ge 0 \\ A \ge 0 \\ P \ge 0 \\ A = x*y \\ P = 2*x + 2*y ...
4
votes
1answer
146 views

Prize collecting steiner tree

I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of ...
12
votes
2answers
709 views

Linear time labeling algorithm for a tree?

I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This ...
2
votes
1answer
2k views

How to analyze the Steiner tree problem?

I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps. 1) Look up what the Steiner tree problem is. 2) Find a ...
95
votes
2answers
30k views

BIT: What is the intuition behind a binary indexed tree and how was it thought about?

A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
3
votes
1answer
761 views

Height of a full binary tree

A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children. I have been trying to prove that its height is O(logn) unsuccessfully. Here is my work so far: I ...
-1
votes
2answers
3k views

Longest path in undirected tree [duplicate]

Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge ...
3
votes
3answers
929 views

Find node that splits tree in half

Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the ...
4
votes
1answer
622 views

Algorithm for determining minimal set of covering prefixes

I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set. For instance, if my set is: ...
0
votes
1answer
836 views

Notation Conventions for Tree Data Structures

I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to ...
1
vote
1answer
2k views

Calculating traversal position of a node in a full binary tree, given its path

Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in ...
2
votes
1answer
108 views

Is this data structure a hypertree or only isomorphic trees?

I have a data structure described as following: - It's a collection of trees. - Each tree has the same structure. - Each tree has information of diferent nature. ...
2
votes
1answer
2k views

Why does a suffix tree have a linear number of nodes (relative to input string size)?

Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.
9
votes
3answers
41k views

Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

In my Java class, we are learning about complexity of different types of collections. Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
3
votes
1answer
154 views

Constructing a tree from disjoint graphs

I will preface my question with the definition of a simple tree that applies to my question: A simple tree is an undirected and connected graph with no cycles. I am having difficulty coming up ...
2
votes
1answer
354 views

Size of the universe for van Emde Boas Trees

In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde ...
5
votes
1answer
1k views

Explanation of recursive structure of Van Emde Boas Tree

From Van Emde Boas trees lecture: We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of a bit vector, but shrink the universe size recursively by a square root at each ...
8
votes
3answers
878 views

Finding the height of all nodes in a forest

I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges ...
6
votes
2answers
970 views

Separate all leaves of a weighted tree with minimum weight cuts

This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete ...
15
votes
1answer
378 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
1answer
371 views

What is postorder traversal on this simple tree?

Given the following tree: Which traversal method would give as result the following output: CDBEA? The answer in my study guide is Postorder, but I think postorder would output: DEBCA. Am I wrong?
4
votes
2answers
463 views

Counting trees (order matters)

As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In ...