Questions tagged [trees]

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

2
votes
1answer
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 ...
0
votes
0answers
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 ...
5
votes
2answers
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 ...
1
vote
0answers
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 ...
4
votes
2answers
1k 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
28 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
350 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-...
1
vote
2answers
124 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
56 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
37 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
732 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
68 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
99 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
82 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
32 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
31 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
148 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
260 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
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
58 views

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

Preamble Suppose we have some symbols x, y, ... and wildcards (ξ), ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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: ...
1
vote
1answer
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: ...
1
vote
1answer
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: ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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-...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ? ...
1
vote
1answer
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, ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
7
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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. ...
2
votes
1answer
78 views

Set partition refinement with subtrees

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 ...
-2
votes
1answer
175 views

Obtain data structure able to do reverse range updates

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 ...