Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
0
votes
0answers
11 views
Finding the intervals containing the query interval
Intervals are represented by two numbers, let's say integral numbers. At the beginning we have sequence of given intervals, for example [1, 5], [4, 8], [3, 5]. After that, we have sequence of queries, ...
3
votes
1answer
29 views
How to calculate the minimum number of groups, by grouping groups with capacity together?
I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.
If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
1
vote
1answer
29 views
Greedy algorithm to find Minimum Dominating Set in a tree
Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
1
vote
3answers
27 views
Intuitive proof for a tree with n nodes, has n-1 edges
I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
0
votes
0answers
33 views
Binary search tree with minimum potential
How to construct a n-node binary serach tree such that its potential is the minimum? The size, rank and potential are defined as follows
The size $s(v)$ is the number of nodes in a subtree (include v)...
1
vote
1answer
18 views
Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it
Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the ...
0
votes
0answers
14 views
Algorithm to determine an approximate distribution of leaf node depths in a massive tree
I am conducting some analysis of game trees (often consisting of 10^50 or more nodes). I'd like to determine, in a given game, how deep in the tree the leaf nodes tend to be. That is, how long the ...
0
votes
0answers
14 views
AVL Tree:Deletion proof
Show that at most one node in an AVL tree becomes temporarily imbalanced after the immediate deletion of a node as a part of standard remove map operation.
How should I start and what should I use to ...
0
votes
0answers
8 views
Tree data structure for streaming write heavy transactional data
I have to cache highly transactional, rapidly changing data in memory. This data is big: to the tune of 100s of GBs.
I want to be able to stream this data from memory of one computer C1 to the memory ...
1
vote
1answer
43 views
Checking if the graph provided by a distance matrix is a tree
I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily ...
1
vote
0answers
27 views
Intuition behind balancing of link/cut data structure
My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no ...
1
vote
2answers
167 views
Is there a name for this graph search strategy?
The standard implementation of breadth-first search looks like
...
1
vote
0answers
30 views
Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))
So this is a question within a bigger question for which I've reduced to this so far:
If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
0
votes
1answer
178 views
Inorder Traversal of the Ternary Tree
According to wikipedia , Definition of In-order Traversal on Binary Tree :-
...
0
votes
0answers
7 views
Alternative technologies/theories for a “Git for Structured Graph Databases”
Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...
0
votes
1answer
19 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
36 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
39 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
55 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
26 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
66 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
17 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
91 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
32 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
67 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
353 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
68 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$...
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
67 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
101 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
53 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
235 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
72 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
50 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
68 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
44 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
10 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
244 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
412 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
22 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
292 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
66 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
32 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
23 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
719 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
63 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
56 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 ...
