# Questions tagged [trees]

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

677 questions
Filter by
Sorted by
Tagged with
32 views

### BVH construction without sorting

Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives ...
22 views

### sum selected nodes of a set in $\log n$ time

Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation ...
65 views

### Can Edge Belong to a cycle if it is part of multiple BFS products

Given a simple connected undirected graph. with V vertices and E edges. Let e be some edge from E. If I perform |V| different BFS runs - meaning started each time from a different vertex - and in ...
19 views

### LOUDS Succinct Tree Representation

I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
26 views

### Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an "Example of a heap storing 13 entries with integer keys. The last ...
55 views

### What does it mean that B-tree leaves carry no information?

According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.". What does it mean that they carry no information? ...
12 views

### How do you prove that this tree path calculation function works, from first principles mathematically?

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
56 views

### Are some algorithms inherently recursive?

Are some algorithms inherently recursive? As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise. I am asking because I struggled to ...
110 views

### How to detect “tree-able” set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
28 views

### Why does the formula floor((i-1)/2) find the parent node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with parent ...
24 views

Recursive ...
14 views

### How to convert recursive language grammar tree into automaton for optimal parsing?

So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees. ...
26 views

### What is a dominator node and a dominator tree?

I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node: a node d dominates a node n if every path from the entry node to n must go ...
13 views

### Derivation tree and Productions from left most derivation of string

How can one find Derivation tree and Productions of a Grammar from left-most derivation and string used? I was given input string x = abaccacaa , left most derivation lder(x)=(1,2,1,3,4,1,3,5) and two ...
139 views

### Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?

The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
47 views

### Given two identical DOM trees find same node in tree B

So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'. I can solve it in two ways - Start at the given element and traverse up to ...
56 views

### Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
25 views

### Basic Binary search tree query

Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
23 views

### Recording a histogram in a tree exhibits strange best case

The task is to record a histogram from a streaming data source. One data point is, say, a 16 bit integer. The maximum multiple of one data point before the stream ends, is < 2^32. The main ...
65 views

### Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck. Given a binary tree where each node in the tree can either be selected or unselected, ...
22 views

### What is the most efficient way to turn a list of directory path strings into a tree?

I'm trying to find out the most efficient way of turning a list of path strings into a hierarchical list of hash maps tree using these rules: Node labels are delimited/split by '/' Hash maps have the ...
37 views

85 views

### Databases and B-Trees: What are Keys and how are they related

I confused about the description & definition of "key" occuring as terminology for databases and b-trees. In first case dealing with theory of databases a key is defined as a choice for ...
18 views

### What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of ...
179 views

### Minimum cost of “signal” cover in a tree with DP

I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ ...
42 views

### Shortest path in BST

Given a Binary Search Tree and two elements $e1$ and $e2$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked ...
51 views

### Name of BFS variant with multiple queues with different priorities

Is there a name for the following variant of BFS that operates on trees with non-root starting point?: Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
35 views

### Product of all nodes except for one in Binary Tree

Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...
397 views

### Facility location on a tree

Question: Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered. An antenna of strength 0 can only ...
25 views

### Does this algorithm traverse trees in logspace?

Does this algorithm traverse trees (correctly) in logspace? Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
46 views

### Can the structure of a “Complete Binary Tree”, be uniquely identified if only its pre-order or post-order or in-order traversals are given?

I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order. The following is the definition of a complete ...
50 views

### Marginal Probability of Generating a Tree

Fix some finite graph $G = (V, E)$, and some vertex $x$. Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows: Let $T_0 = \{ x \}$. For $0 < n \leqslant N$ i. Let ...
46 views

### Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?

I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree. The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input ...
64 views

### Convert tree with recursive relationship to parent-child tree

Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good ...
352 views

### Find height of a ternary tree

Ternary heap is like a binary tree, just every node can have up to $3$ sons and not $2$. I try to bound the number of nodes in the heap, $n$, using the height of the heap $h$. The solutions get to: ...
12 views

### What is the insertion algorithm for an AVL tree with balance constraint of 2?

What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
24 views

### modifing CYK to compute the number of different parsing trees of a given sentence

Given a CFG in Chomsky Normal Form and a sentence s. I want to count the number of different parsing trees that parses s. assuming I know how to change the CYK algorithm so it would count the number ...
65 views

### Trees with duplicate nodes and path cancellations

I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
18 views

### Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key). In general ...
25 views

### Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
8 views

### Minimal t needed in B tree for the lowest reading time

I've got an assignment, which I was asked to calculate the minimal t needed in a B tree, to have the optimal searching time. So here it is: We've been told that in a specific B tree, with unknown t, ...
We are given a tree with $n$ vertices and some of the vertices act as a "hotspot". We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest ...