Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
22 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
65 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
18 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
39 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'...
1
vote
2answers
117 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 ...
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 ...
8
votes
1answer
104 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 ...
1
vote
1answer
46 views

Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
0
votes
1answer
38 views

How to build tree from graph with specific property

We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written. We need to build tree such that for each node $i$, all nodes in the ...
5
votes
1answer
3k views

Time Complexity to find height of a BST

Below is a question I was asked in an Interview What is the best case time complexity to find the height of a Binary Search Tree? I answered it explaining using the below algorithm $\mathrm{...
0
votes
1answer
44 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 ...
0
votes
1answer
39 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 ...
5
votes
2answers
725 views

Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

This is from CLRS problem 24.3-5: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$ . Give ...
-1
votes
2answers
6k views

what is the advantage of using threaded trees?

Since a binary tree with $N$ nodes has $N+1$ NULL pointers (across leaves), half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a NULL left ...
1
vote
1answer
83 views

Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
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: ...
4
votes
1answer
49 views

How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
1
vote
0answers
82 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) ...
4
votes
1answer
47 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 ...
1
vote
1answer
192 views

Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
0
votes
1answer
98 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
103 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 ...
1
vote
1answer
1k views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
1
vote
1answer
31 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
1answer
28 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
2answers
55 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
1answer
49 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
15 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 ...
19
votes
1answer
753 views

Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
0
votes
1answer
26 views

Tree search returning parents and children

I've a flat structure where a node references its parent instead of children class Node(int Id, Node Parent, string Data); Given a list of all nodes, and a ...
0
votes
2answers
6k views

Order of a leaf node in B+ Tree

Going with the definition, that order of a B+ tree is the maximum number of children a node can have. What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node ...
1
vote
1answer
42 views

Is “sparse subtree” an appropriate term for what I describe in this question?

Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original ...
1
vote
2answers
1k views

Find a node with maximum distance from query node in a tree

I solved this problem from codechef: problem link and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ ...
0
votes
0answers
26 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 ...
2
votes
0answers
47 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 ...
5
votes
1answer
364 views

What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree ...
2
votes
1answer
583 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
0
votes
0answers
22 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 ...
3
votes
1answer
144 views

minimum and maximum nodes of MultiWay tree of height h

I know that it doesn’t have to be balanced so in theory given that the height of the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first ...
4
votes
4answers
1k 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 ...
1
vote
1answer
147 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
0
votes
0answers
97 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 ...
3
votes
1answer
81 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
0
votes
0answers
24 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. (...
1
vote
1answer
135 views

Merge Leaf labeled trees [closed]

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...
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 ...
5
votes
1answer
465 views

What are these tree transformations called?

I want to transform a general rooted, node-labeled tree into a related binary tree. I came up with four different schemes ("left shallow", "right shallow", "left deep" and "right deep" binarization) ...