Questions about a special kind of graphs, namely connected and cycle-free ones.
0
votes
0answers
29 views
Proving BFS can find the furthest node from root
I am trying to prove this post in a different way. I'd like to prove it using the following scheme
During the first BFS run, if we keep track of depth, once the search has terminated, the node with ...
0
votes
1answer
14 views
Tree with alternating types of nodes
Suppose that I have a tree where each node is either of type A or type B.
Nodes of type A ...
0
votes
1answer
25 views
Can a node of Radix tree which represents a valid key have one child?
Wikipedia says:
a radix tree is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.
Now they are situations ...
0
votes
1answer
22 views
Time Complexity of the Kruskal Algorithm after sorting
In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
1
vote
0answers
21 views
Extracting room voids in a house
I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house.
In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
0
votes
2answers
43 views
In Breadth-first search and depth-first search what is the purpose of visited flag
In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932
...
0
votes
0answers
22 views
Form a Tree having minimum diameter
I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.
However, I looked for the solution, and the solution goes like this.
If the diameter of ...
0
votes
1answer
59 views
Understanding SLDNF-forest
I am trying to understand this program and the respective forest. This is from the book Logic,Programming and Prolog by Ulf Nilsson.
Question:
In the main tree, why from ←off_gound(a) can you ...
2
votes
1answer
16 views
Array of overlaping ranges
Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.
Example:
Ranges:
[red: [1,11], black: [15,16],yellow: [5,9], ...
4
votes
2answers
90 views
Data structure for a tree of points moving in space
I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "...
1
vote
1answer
28 views
Could a Van Emde Boas tree be used for storing matrices?
I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix.
I was wondering if ...
2
votes
1answer
54 views
How to find all topological sortings of a special DAG in O(N^2)
I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.
https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum
...
2
votes
2answers
281 views
Encoding (binary) trees using lambda calculus
I'm new to lambda calculus, and I read all kinds of interesting stuff about encoding data types as functions. Church booleans, numbers and lists.
https://en.wikipedia.org/wiki/Church_encoding
Is ...
0
votes
0answers
16 views
How to solve question answer questions using trees and graph theory?
Good evening! I'm doing an internship at Ecole Normale Supérieure of France, where they create their scholars, and I encountered a dataset I wanted to solve using graphs...
I. The challenge ? ...
0
votes
0answers
35 views
Algorithm for generating all unlabeled trees with n nodes?
How can one generate all unlabeled trees with $\le n$ nodes?
That is, generate and store the adjacency matrices of those graphs? (not just count them)
Visualization of all unlabeled trees with $\le6$...
0
votes
0answers
12 views
How to organize m-numbers into a [1..n] depth tree where the branching factor is variable and the nodes at the lower levels add up to their parents?
I need to organize a set of energy consumption numbers to determine the metering strategy (which would be tree-like) where the lower nodes add up to their parents(with some tolerance).
How do I do ...
1
vote
1answer
30 views
How to test if my implementation of tree/graph data structures are correct?
I've recently implemented RB tree, B-Tree and vEB tree. I was wondering however if there's any rule of thumb for testing if my implementation are actually correct.
Is there any reference that can ...
1
vote
2answers
45 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 ...
2
votes
2answers
97 views
What is the name of a rooted tree whose nodes may have edges to their descendants?
A tree is a special kind a graph.
However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if ...
1
vote
1answer
43 views
How does SpaCy make its dependency tree?
I discovered that SpaCy had the ability to make dependency trees. For instance given a question “To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?”
We can create its dependency ...
1
vote
0answers
44 views
How to find the maximum size of a B+ tree?
I came across this paper (page 16) which explains how to calculate the size of B+ trees.
According to it the maximum number of nodes at level $i$ is $2(n/2)^{i-1}$ for a B+ tree of order $n$. Thus a ...
2
votes
1answer
43 views
Minimum number of nodes in AVL tree
Let T be an AVL tree of height 3. What is the smallest number of entries it can store? Note that a tree with one node (only the root) has the height of zero and stores one element.
The only method I ...
0
votes
1answer
31 views
Conditions for a node to be a leaf node on DFS tree
Question:
Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node on the DFS tree. The condition must be in ...
-1
votes
1answer
57 views
Do we always get the same set of edges after running Kruskal's algorithm on a single graph?
I think it should be false because there may be more than one edge with the same weight.
2
votes
1answer
36 views
Selecting a subtree in an array representation of a binary tree
Consider a zero-indexed array representation of a binary tree (as in a binary heap), where
0 is the root
The left child of i is ...
0
votes
0answers
8 views
How to determine R-Tree MBR Nodes?
I understand the concept of an R-Tree and how it is used to spatially index and store geometric objects such as polygons and points, but I am not sure how to construct it by choosing MBRs that group ...
5
votes
2answers
226 views
Is there a name and efficient algorithm for this Tree Traversal method?
Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.
I want to traverse this type of ...
1
vote
0answers
25 views
Generate a random tree population
Given
a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees ...
3
votes
2answers
333 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{...
1
vote
0answers
20 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
1answer
287 views
Is every AVL tree a BST or just BT?
I was going through the concepts of AVL tree and came across the definition of AVL tree from the wiki.
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-...
0
votes
2answers
62 views
What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?
What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?
Example:
...
0
votes
0answers
27 views
How many roots are there in an undirected root
Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
1
vote
0answers
20 views
Building segment tree to find minimum suffix sum in range
Let's say we have array $A$ of $N$ integers, each of them in the range $[-1, 1]$. We define an array $B$ of $N+1$ integers, such that $$B_{N+1} = 0, \\B_i = A_i + A_{i+1} + A_{i+2} + \dots + A_{N}= ...
6
votes
1answer
718 views
What algorithm should I use to find a minimal tree that include certain nodes within a graph?
Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or ...
3
votes
1answer
59 views
Find the shortest sub-tree with node deletion
Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ i.e. its children in $T$ and $p(v)$ be its in-neighbor ...
3
votes
1answer
30 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 ...
0
votes
0answers
37 views
Measuring how “balanced” a binary tree is
I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close ...
0
votes
0answers
11 views
Hierarchical Parallel Processing Machines
Introduction
I am wondering if there is a generalization of parallel processing / asynchronous communication that explains/models how to deal with a hierarchy of parallel processes. Mainly looking ...
0
votes
1answer
30 views
The relationship between degree and the number of leaves of a tree?
What is the relationship between $\text{deg}(T)$ and the number of leaves of $T$, if $T$ is a tree?
0
votes
1answer
31 views
A tree which each node selected as a root results in a different topology?
Show that, for every n >= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.
2
votes
1answer
36 views
Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer?
Here is the problem I tried to solve. Finally, I gave up and found a solution which was correct. Here is it.
Here is the problem description:
For a undirected graph with tree characteristics, we ...
4
votes
1answer
167 views
Cover k edges to minimize the length of the longest uncovered path in a tree
You are given a tree $G\langle V, E\rangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path's ...
1
vote
0answers
31 views
Find the minimum visit time on tree
A tree is provided which has $n$ nodes and each edge of that tree has a certain length. There are $M$ persons on the tree, numbered 1 through $M$. For each valid $i$, person number $i$ starts at time $...
1
vote
0answers
14 views
Splay trees: why are depths of nodes on the access path halved?
The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:
Splaying not only moves x to the root, but roughly halves the depth of every node ...
2
votes
1answer
38 views
What is a not-well-founded cotree?
I'm reading the paper "Dual of substitution is Redecoration".
And I'm struggling with understanding the usage of the word "not-well-founded cotrees".
what is a cotree compared to a tree ? I suspect ...
0
votes
0answers
17 views
Fibonacci serial with trees
Hello guys i am wondering about the next question and kinda need an assistants,
i tried to prove by induction but i don't understand the basic step.
lets say F2, so this tree got 2 sons, left and ...
0
votes
0answers
12 views
Name for number of branches of a tree
I'm working with trees in a project where I need to test various tree-making algorithms and their outcome. A frequent quantity I look for is the number of branches of a tree. Is there a commonly used ...
3
votes
1answer
139 views
$O(n\log n)$- algorithm for finding tree root
All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$. We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain ...
0
votes
0answers
28 views
Why are red-black trees still preferred over weak AVL trees [duplicate]
Both have a maximum height of 2*logn
WAVL trees have a maximum height of 1.44*logn if built using only insertions. If built using both insertions and deletions, then inserts will tend to restore the ...
