Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
1
vote
1answer
36 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, ...
2
votes
1answer
64 views
Suggest a Data Structure To Manage 2 Sets
I was given the following problem which really baffled me, and I would like some guidance in solving it.
I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
0
votes
0answers
32 views
Algorithm to change order of tree
I'm looking for an algorithm name to change the order of the levels of a tree. I've done something that works but there's a lot of code and the $ O(n) $ is very bad.
Here's an example, let say there ...
0
votes
0answers
60 views
Find longest path in minimum spanning tree
Given an undirected MST with positive weights how can the longest path be found?
Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've ...
0
votes
0answers
22 views
Is the following “get tree next key” algorithm correct? [closed]
I want to create a non-recursive algorithm for finding in a binary search tree the smallest entry larger than a given key. The tree cannot contain duplicates. There are parent pointers for every node.
...
3
votes
0answers
72 views
How to cover holes with disks of a fixed radius? [closed]
So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These ...
1
vote
1answer
26 views
Merging and Unmerging Sets of Trees Efficiently
Background
Given multiple trees, I'd like to merge all of the them and be able to efficiently unmerge arbitrary trees in the set. For example, here are some JSON trees:
Tree 1:
...
3
votes
0answers
37 views
Tree Automata Operators
I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows:
...
3
votes
2answers
46 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 ...
0
votes
0answers
35 views
Real-world scenario for a theoretical problem on trees
Suppose one has a tree with each node weighted with a tuple (say, some fixed $2$ dimensions, for now) of integers. Now we query the tree with two vertices $x$ and $y$ and a range $[a,b]\times [c,d]$, ...
3
votes
1answer
46 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, ...
0
votes
1answer
25 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 ...
2
votes
2answers
50 views
Size of tree decomposition
Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I ...
0
votes
0answers
18 views
Message Passing Algorithm and Implementation
I have a tree T with N nodes (Min-Span-Tree of a graph), and what I am gonna do is to calculate for each node Vi, the number of ...
0
votes
0answers
49 views
How to find the length of maximum subarray sum in segment tree query?
Problem: Given an array with size$\ n $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is ...
0
votes
0answers
38 views
Unite a forest if you know each tree's parent
I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively ...
1
vote
0answers
43 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 ...
-1
votes
1answer
51 views
Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?
We are given a tree of N nodes from 1 to N where node 1 is the root of the tree.
For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
3
votes
2answers
70 views
How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?
The recurrence I have is
$T(n) = 2T(\sqrt{n-1} + 2) + 1$
I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm ...
3
votes
1answer
45 views
Reversible Merge of Integer Hash Values
Context:
I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
2
votes
1answer
50 views
Time complexity of a tree-based algorithm
I solved a practice interview problem that was sent me by Daily Coding Problem mailing list. I am now curious about the exact time complexity of my solution.
Problem Statement
Given the mapping a =...
0
votes
2answers
115 views
prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves
I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction
*Edit: my professor had a significant typo in this assignment, I have attempted ...
1
vote
1answer
66 views
Is Breadth First Search Space Complexity on a Grid different?
Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:
For example, the flood fill question is described here:
https://www....
1
vote
1answer
34 views
Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert?
Im learning about tree data structures, and had a question that i couldnt find answer to so I came here.
Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it ...
1
vote
1answer
87 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 ...
1
vote
0answers
28 views
How do I implement fixed block storage file system in database from typical file-level file system?
I've a typical parent ID based file system in database and files are physically stored on disks. What I want is to store files in blocks (4096K) of fixed size.
Chunking can be used I found, but how ...
2
votes
0answers
99 views
Join Order Optimization
Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player
What is the optimal join order?
Based on the schema on the following picture:
I am suppoused (and that's what I tried) to use ...
1
vote
1answer
25 views
A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher
Referring to these notes regarding DFS - Click Here
They refer to the following claim that follows Definition 0.2. as observation:
A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and ...
1
vote
2answers
42 views
Term for the tree of all paths starting from a given vertex in a graph
What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?
This is the tree that is implicitly or explicitly constructed when ...
4
votes
2answers
548 views
Prove that the total distance is minimised (when travelling across the longest path)
Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have ...
1
vote
1answer
37 views
Rooted Tree Isomorphism Algorithm
I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:
Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$.
...
0
votes
0answers
21 views
How does a binary tree waste memory when stored as nodes and references?
I'm researching binary trees and came across this section describing storage methods.
It states that:
In a language with records and references, binary trees are typically constructed by having a ...
0
votes
0answers
93 views
How many maximum height AVL trees given height?
I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that ...
2
votes
0answers
22 views
Construct a lambda term from a Böhm tree
Given an acyclic graph, how can I build a lambda calculus term such that this graph is the term's Böhm tree?
If the Böhm tree is a finite tree (so the result is a strongly normalizing term).
If the ...
0
votes
0answers
37 views
Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers
So you can store a binary tree without pointers using a 1-D array:
Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :
The values of ...
1
vote
0answers
21 views
Elegant or readable way to store tree by user [closed]
Sorry if my title or question is unclear. I lack the vocabulary to formulate it properly.
I've got a classical tree structure with several layers.
I have to manage authorization for each user, as not ...
1
vote
1answer
35 views
Uniformly random iteration of subtrees
I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $...
0
votes
0answers
14 views
Trie or no Trie for 1,000 page document or searchable BigInt dataset
Tries seem to be good at storing and querying small strings, like keys to a dictionary.
What I would like to know is if there is anything better for storing large strings such as a 1,000 page ...
0
votes
1answer
66 views
Dynamic Programming Problem on Tree
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
0
votes
0answers
9 views
Converting a cyclic digraph to an approximated tree
I have a digraph that represents a taxonomy of sorts, where nodes are "concepts" (i.e., person, animal, plant, etc) and the edges represent an is-a relationship. Hence, we can have ...
1
vote
0answers
32 views
Searching Algorithm on Connected Graph
This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math.
Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
1
vote
0answers
36 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 ...
0
votes
0answers
49 views
Dynamic perfect hashing, FKS Scheme
The FKS scheme uses a 2-level hash function. The first hash function is to partition the elements of the universe $\mathcal{U}$ into the dictionary $\mathcal{S}$. Obviously many elements of $\mathcal{...
1
vote
0answers
17 views
Does keeping underflowed nodes unbalance the R-tree?
When deleting nodes from an R-tree, if a branch underflows, then it's meant to be dissolved and its children are meant to be reinserted into the tree. But most R-tree implementations that I've seen ...
8
votes
1answer
68 views
Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?
As an example, here are all possible trees for the case $k=3$:
On each node written is its arity (= the number of children).
While this should be solvable by dynamic programming, I think there was a ...
2
votes
1answer
50 views
Algorithm to find the two closest elements in a BST
For example, consider an AVL tree:
Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, ...
2
votes
1answer
40 views
What, if any, is the term for a node whose children are all leaf nodes?
More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions:
- It has >= one child
- Any children that it has are all leaf nodes.
0
votes
0answers
16 views
Is there a specific search paradigm for finding pairs in a set?
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
1
vote
1answer
35 views
Polynomial time algorithm - Matching pairs of vertices
Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
2
votes
3answers
121 views
Finding number of edges with weight less than k on the path between two nodes in a tree
You are given a tree with $n$ nodes and $n-1$ edges. Each edge has a weight. There are $m$ queries. In each query you have to answer the following question:
How many edges are there in the path ...
