# Questions tagged [trees]

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

677 questions
Filter by
Sorted by
Tagged with
0answers
48 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 ...
2answers
252 views

### Is there a name for this graph search strategy?

The standard implementation of breadth-first search looks like ...
0answers
335 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 ...
1answer
3k views

### Inorder Traversal of the Ternary Tree

According to wikipedia , Definition of In-order Traversal on Binary Tree :- ...
2answers
76 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 ...
1answer
278 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 ...
1answer
898 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?
0answers
22 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 ...
2answers
331 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 ...
0answers
62 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 ...
1answer
128 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 ...
1answer
20 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], ...
2answers
115 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 "...
1answer
93 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 ...
1answer
662 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 ...
2answers
1k 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 ...
2answers
677 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$...
1answer
76 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 ...
2answers
632 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 ...
2answers
119 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 ...
1answer
320 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 ...
0answers
2k 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 ...
1answer
466 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 ...
1answer
619 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 ...
1answer
250 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.
1answer
159 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 ...
2answers
622 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 ...
0answers
36 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 ...
1answer
7k views

0answers
93 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 ...
1answer
118 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 ...
0answers
41 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 ...
1answer
839 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 ...
1answer
31 views

### The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
1answer
68 views

### E-Unification: “Goal seeking” pattern matching between directed trees

Preamble Suppose we have some symbols x, y, ... and wildcards (ξ), ...