Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
31 views

Determine minimum and maximum number of leaves on a complete tree

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$. I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
-3
votes
0answers
36 views

What are some generalizations of the tree diameter?

I am specifically interested in extensions and generalizations of the diameter concept on graphs. I can't find anything relevant in google scholar. I have a certain result about tree diameters that ...
1
vote
1answer
41 views

Count total number of k length paths in a tree

This is a question from a competitive programming competition. Given a tree with n nodes and a number k, find the total number of paths of length k in that tree. I know for a fact that a solution can ...
3
votes
2answers
108 views

Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
2
votes
1answer
28 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 ...
0
votes
0answers
19 views

Traversing/comparing tree structures with only parent references

Consider a tree structure with nodes containing references to only their parent. So, the root node's parent will be null. This tree represents a class hierarchy. The goal is to search such a tree for ...
2
votes
0answers
60 views

What's the number of leaves in AVL tree

How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree? I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
1
vote
1answer
32 views

Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?

I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed. The question is why is there the ...
0
votes
0answers
13 views

Does this kind of “conversation tree” has a specific name?

Does a Tree of infinite width and depth where each node represents a syntactically valid response to (a node of) a previous response to which it's connected via an edge has a specific name? (It seems ...
0
votes
1answer
34 views

How to delete a node from BST tree with 2 chidren?

I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion ...
3
votes
2answers
44 views

Joining line segments to make tree

Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
3
votes
0answers
53 views

Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
1
vote
1answer
32 views

Prove G have a single MSP

We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?
0
votes
2answers
75 views

Enumerate all paths of length 3 in a given tree T

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.
0
votes
0answers
17 views

Counting nodes within K distance from set of given nodes in a tree [duplicate]

I was going through this article https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/ The question says: Given an undirected tree with some marked nodes and a positive ...
1
vote
0answers
21 views

Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
1
vote
0answers
44 views

Red-Black tree with index

I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index. So if I have the function: $\text{insert}(root, value, index)$ it will ...
0
votes
1answer
20 views

Finding most likely tree over a semilattice

If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees. Now assume that each semilattice edge is annotated with a transition probability. In addition, let'...
0
votes
1answer
30 views

Name for Turning DAG into redundant tree

I am looking for a term: How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
1
vote
2answers
124 views

Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$ I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$ I ...
1
vote
1answer
49 views

Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
8
votes
1answer
105 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 ...
0
votes
0answers
23 views

how to construct a tree using root tree's code?

The Question is if we are given a binary code how construct a tree using that code? There was a question as follows: By root tree's 000101001111 code, reconstruct that tree. and the complete answer: ...
1
vote
0answers
129 views

Data structure for storing strings

I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) ...
0
votes
1answer
126 views

How to answer multiple queries for a tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each ...
2
votes
0answers
104 views

How to query the tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each ...
0
votes
1answer
54 views

Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

Here's the start and the vernacular I'm using. ...
0
votes
1answer
83 views

Leaf nodes of B+ Tree

I have a b+ tree and i want to find the record associated with a specific key Ki. So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
1
vote
1answer
32 views

Average number of full nodes in rooted m-ary tree

I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e., $$ \mu_{n}^{(m)} = \frac{\# \text{full nodes ...
0
votes
0answers
16 views

Traverse tree collecting nodes combinations

Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts. Parts can be required - every build must contain them. Parts can be optional. Parts ...
0
votes
1answer
55 views

A* algorithm example explained

I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a ...
0
votes
0answers
28 views

How to find running time complexity of divide and conquer method without Master Theorem

I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
4
votes
1answer
48 views

How to find all the edges shared by all diametral paths of a tree?

A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are ...
2
votes
0answers
48 views

How to solve following tree problem?

Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very ...
0
votes
0answers
26 views

RB trees from any balanced BST?

Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be ...
0
votes
1answer
48 views

Merge nodes in a graph to form a tree

I have an undirected graph which may have 2 edges that connect the same pair of nodes. A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a ...
0
votes
0answers
127 views

Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
0
votes
0answers
29 views

Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
0
votes
2answers
98 views

How to do a reverse topological sort using depth first search?

I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
0
votes
0answers
13 views

Efficiently calculate values based on subsets of a list

Let's say I have a list of items, each of which has some value Eg. L1 = [A, B, C, ...] And another list of items L2: [1, 2, 3, ...]. Each of the items in L2 needs to calculate the max value of a ...
0
votes
1answer
41 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
4
votes
1answer
161 views

Min Fibonacci Heap - increase key

I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
1
vote
0answers
14 views

Minimum Weight Binary Spanning Tree

Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every ...
1
vote
0answers
17 views

Directed Trees: Finding all the edges and vertices in a specific direction

I am an electrical engineer without experience in graph theory. However, I have a problem which I believe can be solved by graph theory. We have a directed tree, such as the one below. We want to find ...
0
votes
0answers
105 views

Minimum number of moves to reach a grid point by modified knight in variant chessboard

I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://...
0
votes
0answers
11 views

Depth of an R-tree, given $m$, $M$ and number of elements

Simply: what is the theoretical maximum, minimum or expected depth of an R-tree given $m$ minimum $M$ maximum elements in a node, with $N$ amount of nodes?
2
votes
1answer
81 views

How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with. For example: tree 1 ( (a, b), (c, d) ) Imagine that each tree split represents the function "add", then ...
0
votes
0answers
11 views

Is Edmonds' Matroid partitioning algorithm optimal w.r.t lexicographical order?

We all know that, given a matroid $(E, \mathcal{I})$, Edmonds' Matroid partitioning algorithm will result in a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with optimal (...
3
votes
1answer
64 views

Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices. Thus, there are total nC2 or n(n-1)/2 such ...
2
votes
1answer
169 views

Are all foldable data structures also recursive?

I was checking what Wikipedia has to say on reduce. It says: In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order ...