# Questions tagged [trees]

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

554 questions
62 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 ...
14 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 ...
330 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 ...
33 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 ...
1k views

68 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 ...
70 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 ...
14 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 ...
223 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 ...
24 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 ...
58 views

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

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

### Optimal data structure for sorted list

Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)". Even though B-trees are a generalization ...
205 views

### How does a Trie work?

Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree. The problem though is that after reading ...
36 views

### Choose minimum subset of edges in tree that connects all important nodes

Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$. We want to choose subset of edges of the tree such that: For each two important nodes at least one edge ...
114 views

### A way to convert a binary tree into a grid

Wondering if there is a way to convert a binary tree into a grid such as this: ...
88 views

### Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties

What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties: ...
389 views

### How a range query works on a simple B+tree

Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following: ...
310 views

### Infix search in millions of strings

Let's say we have millions of strings (each of them < 100 characters): alpha allo blah hello world orlando ... I know how a binary search tree or a trie can ...
107 views

### Data structure for a single elimination tournament and its implementation

I want to implement a tournament managing software , something like challonge(https://challonge.com/) and am currently stuck at the data structure to be used. I read up on tournament trees and a ...
73 views

### Transform 2D range query matrix into segment tree to make memory usage lower

Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-...
25 views

### In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a ...
129 views

### Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
34 views

### Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...
79 views

### Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, ...
44 views

### Finding a certain subset of a weighted tree

Given a rooted tree with $n$ weighted nodes and a number $1\leq k\leq n/2$, what is an efficient algorithm for finding a subset of the nodes having $k$ elements no node being an ancestor of another ...
288 views

### How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
105 views

### Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
32 views

### Minimum edge cover with a constraint

An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each ...
19 views

### Doubt regarding deletion from a B-tree

After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for ...
99 views

### Prefix Sums in Mutable 2D Array

Suppose I have a 2D array M[n][n] of integers (in fact, binary is fine, but I doubt it matters). I am interested in repeated queries of the form: given a coordinate ...
32 views

### Cross link suggestion algorithm that distributes and spans all links as fast as possible without loops

I am implementing a topic suggestion system to a website. The aim is to add links to the left panel of each topic. For example, I opened the topic named "topic1", left of the page should show 5 ...
49 views

### Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this? I know ...
55 views

### Complexity for find pairs with sum - BST

I have written an algorithm for find all the pairs in a BST which have a given sum. ...
In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary ...
For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to ...