# Questions tagged [trees]

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

671 questions
Filter by
Sorted by
Tagged with
23 views

### Are some algorithms inherently recursive “like”?

Are some algorithms inherently recursive "like" ? As in, rewriting it in tail-recursive/iterative form a stack is still needed. Struggled to implement ...
101 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 ...
20 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 ...
17 views

Recursive ...
12 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. ...
22 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 ...
12 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 ...
129 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 ...
26 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 ...
54 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 ...
64 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

84 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 ...
16 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 ...
178 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)$ ...
40 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 ...
44 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 ...
34 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 ...
393 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 ...
49 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 ...
52 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 ...
201 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?
22 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 ...
63 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, ...
71 views

### Distance queries on Tree with hotspots

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

### What's the name of this tree-like data structure?

I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties: It consists of nodes and leaves It has a single root element Both nodes ...
26 views

### Understanding recursion tree for withdrawal formula

$$T(n) = T(n-a) + T(a) + cn$$ Now the solution says that the height of the tree $(h)$ is: $$h = \left \lfloor n/a \right \rfloor$$ And I don't understand why. Maybe I didn't understand the ...
17 views

### How to reconstruct an existing splay tree by insertion?

I'm trying to figure out the same problem as stated in this question. In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
35 views

I tried to solve the recurrence relation $T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^... 0answers 45 views ### Is there a *natural* problem that is NP-hard on trees, but in P on non-trees? It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong? Question: Is there some natural decision problem on ... 1answer 28 views ### Prove that a red-black tree with$n$internal nodes has height at most$2\lg(n+1)\$

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it? ...