Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
47 votes
4 answers
66k 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'$. ...
e_noether's user avatar
  • 1,289
137 votes
3 answers
48k 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 ...
Nikunj Banka's user avatar
  • 1,545
42 votes
9 answers
62k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
curryage's user avatar
  • 531
3 votes
1 answer
669 views

Expected distance between tree nodes

I have been given a tree with n nodes and n-1 edges with it's weight. There are two people A and B. I have been given a list of nodes of size k. A will pick a random node x from this list and B will ...
Disha's user avatar
  • 33
2 votes
1 answer
6k views

Number of Different AVL Tree

I studying the related question. https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
user3661613's user avatar
4 votes
2 answers
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]$. ...
problemsolverextreme's user avatar
45 votes
2 answers
31k views

What is the difference between radix trees and Patricia tries?

I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a ...
w128's user avatar
  • 553
11 votes
3 answers
54k 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 ...
CodyBugstein's user avatar
  • 2,957
9 votes
3 answers
21k views

Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?
Death_by_Ch0colate's user avatar
4 votes
2 answers
1k views

Edge exchange property of two Minimum Spanning Trees

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T' Then I want to prove ...
sup_user136396's user avatar
1 vote
1 answer
277 views

Minimum cost of "signal" cover in a tree with DP

I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ ...
rn42v's user avatar
  • 47
20 votes
5 answers
625 views

Efficient compression of unlabeled trees

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...
Raphael's user avatar
  • 72.3k
18 votes
3 answers
16k 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 ...
NL - Apologize to Monica's user avatar
17 votes
8 answers
32k views

Why does the formula 2n + 1 find the child node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the indicies of the children of element at index n can be found with $...
Keatinge's user avatar
  • 311
15 votes
2 answers
14k 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 ...
e_noether's user avatar
  • 1,289
11 votes
3 answers
4k views

What are the applications of Rose trees?

I recently found out about the Rose tree data structure, but just going off of a Haskell data definition and the tiny Wikipedia description of it, I've got some ...
Jules's user avatar
  • 632
10 votes
1 answer
162 views

Generate random labeled tree with constrained edge lengths

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes ...
Richard Futrell's user avatar
9 votes
3 answers
7k views

Is the height of the tree the number of edges or number of nodes?

I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree ...
Olórin's user avatar
  • 859
6 votes
1 answer
486 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
t.pimentel's user avatar
5 votes
3 answers
10k views

how is data in a tree stored in memory?

I am not so familiar with trees. How is a tree stored in memory? what is the data structure type used for storing it? As a string?linked list? stack (!)? Or is there some kind of data storage model ...
parvin's user avatar
  • 619
5 votes
2 answers
4k views

Minimum-weight shortest-path tree

How can we compute the shortest-path tree of minimum total weight for a given connected graph? I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one ...
Addy101's user avatar
  • 51
5 votes
2 answers
994 views

MST with half the edges the maximum weight

I have been cracking my head over the following question - You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with ...
Ben Danon's user avatar
  • 125
4 votes
2 answers
552 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 ...
user1419's user avatar
  • 153
4 votes
2 answers
817 views

Minimally extend a tree such that there are no bridges in the new graph

We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph. An edge $e$ is a bridge if the graph with that edge removed is no ...
someone12321's user avatar
  • 1,428
4 votes
4 answers
2k 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 ...
user avatar
3 votes
2 answers
923 views

How to make efficient path minimum queries in a tree?

Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them? My ...
Christopher Miller's user avatar
3 votes
0 answers
487 views

Facility location on a tree

Question: Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered. An antenna of strength 0 can only ...
billo's user avatar
  • 31
3 votes
1 answer
1k views

Finding the minimum number of calls in a tree

I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before. Suppose you ...
Bob Jonas's user avatar
3 votes
1 answer
859 views

How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
user8469759's user avatar
3 votes
1 answer
374 views

Finding the shortest path for synchronized pawns in a maze

I have been trying to wrap my head around this problem, and I just can't get it. We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
mander39's user avatar
3 votes
1 answer
589 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 ...
problemsolverextreme's user avatar
2 votes
1 answer
584 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 ...
smac89's user avatar
  • 137
2 votes
1 answer
99 views

Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
BOB123's user avatar
  • 147
2 votes
1 answer
754 views

Correctness proof for finding weighted maximum independent set for a tree

The maximum weighted independent set for a tree can found out using the following dynamic programming approach. Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } ...
Aniket's user avatar
  • 21
2 votes
1 answer
285 views

Connecting an unconnected forest of subtrees in a graph?

If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other. What is the best way to connect these three trees such that ...
guskenny83's user avatar
2 votes
0 answers
76 views

Using the random forest algorithm to predict vectors [duplicate]

I know this might sound like a newbie question, but bear with me. I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a ...
jeshaitan's user avatar
  • 173
2 votes
2 answers
149 views

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space. The original problem appears here, ...
Yos's user avatar
  • 527
2 votes
1 answer
163 views

What is the name of this function of a tree?

I've written a recursive function of a tree, and I would like to know what it's called! It's not quite the same as the height or the width of a tree, but it seems kind of like a width. Assuming the ...
guest's user avatar
  • 41
2 votes
2 answers
142 views

Distance queries on Tree with hotspots

We are given a tree with $n$ vertices and some of the vertices act as a "hotspot". We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest ...
user avatar
1 vote
1 answer
644 views

Remove range of keys from Binary Search Tree in O(s+h)

I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h) where s is the number of keys to remove and h is the height of the tree. Attempted ...
EpicNicks's user avatar
1 vote
1 answer
162 views

bellman ford and one surprizing fact

I ran into a very surprising local contest problem. after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex v being updated, then v is on negative cycle....
Mokholia Pokholia's user avatar
1 vote
1 answer
79 views

How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$

I try to find tree height such that first i define: $H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$ then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree ...
user avatar
1 vote
2 answers
50 views

Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good

Suppose that I want to enumerate all English language words of length 5. If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. ...
user39430's user avatar
1 vote
0 answers
85 views

Conceptualizing a balance in a DFS traversal [closed]

I'm trying to use the concept of DFS traversal to go through a cycle, and attempt to get a balance of 0 in the end. Each student either owes or is owed some money, so I'm trying to go through all of ...
Andrew Raleigh's user avatar
1 vote
1 answer
2k views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
user avatar
1 vote
1 answer
139 views

Why not use large $k$ in a $k$-ary tree?

Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case. To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, ...
erip's user avatar
  • 113
1 vote
0 answers
231 views

Why the update low value in Tarjan's for the ancestors is not it's low value instead of it's discovery value? [closed]

In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this ...
Kareem's user avatar
  • 111
1 vote
0 answers
96 views

Given a tree find path that maximizes the median of the costs of edges

We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path ...
someone12321's user avatar
  • 1,428
1 vote
0 answers
1k views

Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows: Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a ...
RajS's user avatar
  • 1,647
1 vote
2 answers
979 views

Why can't we just use preorder traversal to check if a tree is subtree of binary tree?

Is preorder traversal enough to check if a tree is subtree of a binary tree? Are there any scenarios which I can miss if I use just the preorder traversal? What other methods can be used to check if ...
Ryan Cyrus's user avatar