Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
32 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 ...
1
vote
1answer
37 views

Why $T(n)=6T(n-1) + n^3$ has such a mess solution?

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)^...
3
votes
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 ...
0
votes
1answer
76 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? ...
0
votes
0answers
36 views

creating a binomial heap with only pointer object references

I have a problem where I must make a binomial heap in Python. I have almost all of the methods working except for the bubbleUp method. The problem I am having is ...
1
vote
3answers
197 views

Minimum-average-cost subtree that is not necessarily spanning

I'm looking for an efficient algorithm for the following problem: Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root)....
4
votes
2answers
135 views

Origin of using “>” to represent child in a tree

What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child e.g. ...
0
votes
1answer
330 views

How do I calculate the probability of a PCFG rule in a parser?

I'm quite struggling with calculating the probability of a rule for a PCFG. I've been looking for examples online and more information, but I am none the wiser. Here is an image of the slides. I ...
3
votes
2answers
42 views

When should we construct trees, graphs to analyse an algorithm?

In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to ...
0
votes
1answer
57 views

Computing all paths from root to the leaf nodes in a tree

I have a this tree, i want to print out all paths from root to all child nodes: NOTE: I wanted to come up with a solution that does not involve passing state between recursive calls. ...
1
vote
1answer
97 views

Finding the longest path of sum $0$ in a weighted tree

How to find the longest path with the sum $0$ in a weighted tree (where each edge is labeled with an integer weight)? In other words, I want to find a path so that the sum (sum of numbers on edges) ...
0
votes
0answers
35 views

Is it necessary that Minimum/Maximum Heap must be a Binary Heap?

I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data ...
1
vote
1answer
42 views

Least common ancestor relative to an arbitrary vertex as root

Consider following problem: Given an undirected tree answer following type of queries. (No. of queries and vertices can be as high as $10^5$) $\text{LCA}(r, u, v)$: Find the Lowest Common ...
1
vote
1answer
50 views

How to generate tree variants of a tree using recursion?

I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion? any help is ...
0
votes
1answer
230 views

Remove range of keys from Binary Search Tree in O(s+h)

I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h) where s is the number of keys to remove and h is the height of the tree. Attempted ...
8
votes
0answers
129 views

MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
1
vote
0answers
24 views

Determining Range of Current Node in Segment Tree

I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
1
vote
1answer
98 views

Complexity of “Subtree of Another Tree”

I wrote an algorithm for a leetcode question. The question asks: Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A ...
3
votes
1answer
85 views

Can one determinize finite automata over infinite trees?

I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with Büchi, co-Büchi, Muller, Rabin, Streett, or parity acceptance ...
2
votes
2answers
487 views

Proving correctness and optimality of a greedy algorithm

Here is a (slightly abridged) problem from Kleinberg and Tardos: Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated ...
3
votes
0answers
40 views

Random linear arrangement of a tree with constrained edge lengths

Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the ...
0
votes
2answers
184 views

How to convert a Complete Binary Tree to a Priority Search Tree in O(n)

There doesn't seem to be any resources on this. I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, ...
1
vote
0answers
13 views

Confusion with “every path from a given node to any of the leaves goes through the same number of black nodes” property of RB trees

One of the properties of Red Black trees is: "every path from a given node/vertex to any of the leaves goes through the same number of black nodes" Two related questions about this property: 1) is ...
1
vote
2answers
719 views

Graph with exactly 2 Minimum Spanning Trees

Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in ...
1
vote
1answer
95 views

Performance of Recursive vs Iterative Solution to “Maximum Depth of a Binary Tree”

I am looking at this question from LeetCode. There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution. My question is in regards to the ...
1
vote
1answer
311 views

Efficiently finding the min-cost path of an AVL tree

It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree: The min-cost path would be 8-6-5. ...
2
votes
3answers
323 views

Can the same node appear twice in a tree?

Can the same node appear twice in a tree? I'm asking about the node object itself, not the node's value. For example, in the following code, a's left and right ...
2
votes
1answer
51 views

minimizing the maximum between a degree of a tree and its height

I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log_kn)$ asymptotically. If I set $k = \frac {\...
1
vote
0answers
25 views

Counting number of binary trees with given node values and root

I came across following problem: Find number of binary trees possible with 2 as roots. Nodes={1,2,3,4,5} There was no solution given. I knew number of binary trees for given preorder is given by ...
1
vote
1answer
38 views

Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$

I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement. I know it's a proof by induction and that the ...
0
votes
1answer
536 views

Determine minimum and maximum number of leaves on a complete tree

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$. I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
3
votes
1answer
1k views

Count total number of k length paths in a tree

This is a question from a competitive programming competition. Given a tree with n nodes and a number k, find the total number of paths of length k in that tree. I know for a fact that a solution can ...
4
votes
2answers
396 views

Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
2
votes
1answer
40 views

Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
3
votes
0answers
335 views

What's the number of leaves in AVL tree

How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree? I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
1
vote
1answer
198 views

Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?

I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed. The question is why is there the ...
0
votes
1answer
848 views

How to delete a node from BST tree with 2 chidren?

I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion ...
3
votes
2answers
79 views

Joining line segments to make tree

Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
3
votes
0answers
62 views

Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
1
vote
1answer
55 views

Prove G have a single MSP

We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?
0
votes
1answer
149 views

Enumerate all paths of length 3 in a given tree T

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.
1
vote
0answers
67 views

Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
1
vote
0answers
203 views

Red-Black tree with index

I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index. So if I have the function: $\text{insert}(root, value, index)$ it will ...
0
votes
1answer
23 views

Finding most likely tree over a semilattice

If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees. Now assume that each semilattice edge is annotated with a transition probability. In addition, let'...
0
votes
1answer
33 views

Name for Turning DAG into redundant tree

I am looking for a term: How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
1
vote
2answers
2k views

Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$ I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$ I ...
1
vote
1answer
489 views

Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
9
votes
1answer
132 views

Generate random labeled tree with constrained edge lengths

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes ...
1
vote
0answers
268 views

Data structure for storing strings

I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) ...
0
votes
1answer
340 views

How to answer multiple queries for a tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each second, the ...

1 2
3
4 5
15