Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
2
votes
1answer
35 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
15 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
33 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. ...
1
vote
1answer
27 views
Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex
How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?
UPD:
Example for n = 4:
insert 60
insert 10
insert 20
insert 50
...
2
votes
2answers
48 views
Finding the k-th smallest ternary sum of elements from three different arrays
The problem goes like this:
Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+...
2
votes
0answers
30 views
Documentation of “bin number” trees
TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
2
votes
1answer
88 views
What is the point of traversing a binary tree in preoder, inorder or postorder?
Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
0
votes
0answers
15 views
How would I optimize a tree-like graph with a significant number of redundant nodes?
Recently, I was looking at the underlying data/implementation of a survey application created using a RPA tool. As a user progresses through the survey, the "decisions" reveal a predominantly tree-...
-1
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
43 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 ...
2
votes
1answer
42 views
Data Structures - Segment Trees
I was learning about segment trees and came across this:
We have an array arr[0 . . . n-1]. We should be able to
1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1
...
1
vote
1answer
40 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
36 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
35 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
19 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 ...
-1
votes
0answers
15 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 ...
-1
votes
0answers
15 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
9 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
45 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
30 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
171 views
Is there a name for this graph search strategy?
The standard implementation of breadth-first search looks like
...
1
vote
0answers
48 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
303 views
Inorder Traversal of the Ternary Tree
According to wikipedia , Definition of In-order Traversal on Binary Tree :-
...
0
votes
0answers
10 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
2answers
31 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
42 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
61 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
59 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
34 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
72 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
98 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
34 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
72 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
375 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
18 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
89 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
81 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
66 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
396 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
89 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
65 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
77 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
47 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
254 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 ...
