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
20 views

Rebalance the following AVL tree after inserting G. You need to show the middle step if it happens. Briefly explain the operations

I recently learned AVL Trees but I still lack a complete understanding of the concept. I understand that an AVL tree is a Binary search tree that checks for the height of the tree, but I still don't ...
0
votes
0answers
26 views

How is red-black tree insertion more effective than avl tree insertion

I'm having trouble understanding why RB tree insertion is called more effective in all sources. It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
2
votes
1answer
53 views

Why recording non-existent children in the pre-order traversal will differentiate different binary trees?

I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
-3
votes
1answer
119 views

Print all nodes which are the endpoint of the diameter of a tree

Given a tree with n nodes, Print all nodes which are the endpoint of the diameter. 1<= n <=100000. E.g. For Above tree answer would be A,B,F,G I tried the O(n2) approach (Running Dfs from each ...
0
votes
0answers
26 views

Removing and adding edges from spanning tree

Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
0
votes
1answer
96 views

Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question : Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
2
votes
0answers
27 views

Shortest path in a tree

Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
0
votes
1answer
26 views

What is the name of a sequence structure where writes in the same area are faster?

I recall reading about a data structure for sequences where writes in the same area are faster due to some kind of caching or structure manipulation. What are some structures that do this? I know a ...
0
votes
0answers
21 views

using TRIE for strings?

I saw the following question online: Init - Initlize data structure in O(1). Insert(s) - Add string s to your Data Structure in ...
0
votes
0answers
34 views

How to trasnform search tree into AVL tree with constant memory and in linear time? [closed]

How to transform search tree into AVL tree with constant memory and in linear time ?
0
votes
1answer
36 views

Query sum of values between lo and hi for a stream of numbers

Suppose you have a stream of incoming numbers that you're storing and at any given instant in time, you want to query the sum of values between a given lo and ...
2
votes
1answer
24 views

Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
2
votes
1answer
48 views

Is this a valid encoding of a tree structure using set theory and a valid way to extract the leaves from it?

I'm looking to formally define a tree and then extract the leaves from it in a concise way. Does this look ok? What is the best way of doing this? $ Y = \{a,b,c,d,e,f,g\} \\ R = \{a \mapsto b, a \...
1
vote
0answers
25 views

Minimal description for tree selection

If you have a tree, where nodes can be either selected or not selected, and you wanted to describe which nodes were selected or not you could either List all the selected nodes and infer the others ...
1
vote
1answer
38 views

Applications of Complete Binary Tree?

Wondering what are the real word applications of the Complete binary trees or Almost complete binary trees where the the last level of the tree may not be complete and all nodes in the last level are ...
0
votes
0answers
20 views

What is the time complexity of comparing two Merkle trees?

I have a simple recursive function that compares two merkle trees and accumulates the differences in the leaf nodes. However, I am unable to measure the time complexity of it. Specifically, I would ...
0
votes
0answers
12 views

Generic real-time message/event matching engine

I'm looking for methods (any kind of combinations of algorithms & corresponding data structures) that can be used as a generic matching engine in case of arbitrary message/event types. Let me ...
0
votes
0answers
10 views

Full analyses of the number of nodes/keys and height of B-Trees

If I'm given a tree with "$k$" keys, or "$n$" nodes and I need to find the minimal / maximal height of the tree, I know that I have to split it into two cases: $i$. The tree is ...
3
votes
1answer
46 views

Observations about the structure of an optimal Binary Search Tree

My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees. I am confused about the following sentences: Consider any subtree of a binary search tree. It must contain ...
2
votes
0answers
23 views

Minimum unrooted binary spanning tree

Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints: tips have degree $1$ internal vertices ...
1
vote
1answer
49 views

More efficient way to parse array into binary search tree

Let's assume I have array which I need to parse into binary tree ...
0
votes
0answers
10 views

Dimensional reduction of quadtree influence on clustering with dbscan

Let's say we take a quadtree of 50 dimension and apply dimension reduction(Assume the dimension reduction works well). Why does the dimension reduction not influence the clustering with DBSCAN(Mintpts:...
0
votes
1answer
21 views

Children of internal node in a quadtree with high dimensionality

Let's say for example we have 1000 points and 50 dimensions. And we build a quadtree where each node represents a 50-dimensional box and is divided by splitting the box into smaller boxes that are ...
-3
votes
1answer
150 views

If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x

Statement: If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x. Hint: Begin by computing a DFS tree, and prove an upper bound on its height. I am supposed to prove the ...
4
votes
0answers
50 views

Collision detection with vary constraints

I have an edge-weighted tree, and for each leaf of the tree, there's a corresponding point on the 2D plane. For each pair of points $u$ and $v$, let $d_{uv}$ be the distance of the corresponding ...
2
votes
1answer
33 views

Optimal online algorithm to guess the tree

I have a tree on $n$ vertices. Your goal is to find the adjacency list for it. $n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
0
votes
0answers
17 views

Partition in a tree shaped distributed network

We are given a synchronic undirected tree shaped network, with $n$ indexed nodes. We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given. We need to ...
0
votes
0answers
36 views

A claim regarding Huffman tree?

I saw the following claim: Given $Q=\{1,2,\dots,n\}$ and $f$ (positive function) such that: $$f(1)>f(2)>\dots>f(n)>f(1)/3$$ Then there are leafs at maximum 3 different levels of Huffman ...
3
votes
1answer
57 views

Algorithm to Compute High Water Mark

I saw this algorithm question which is as below. There is a server that receives request Ids that are positive integers. The High Water Mark (HWM) for the server at any instant of time is defined as ...
0
votes
0answers
14 views

Research on Tree Automata/Tree Transducers for implementing Tree Generators

I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically ...
0
votes
0answers
20 views

Alter Sankoff's Algorithm to give all optimal solutions

I'm trying to find a way to alter the Sankoff's Algorithm so it will trace back all the optimal solutions and not only one. Is it possible?
3
votes
1answer
85 views

Representing abstract syntax tree as a graph

Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code? The goal and application ...
3
votes
2answers
190 views

Edge exchange property of two Minimum Spanning Trees

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T' Then I want to prove ...
0
votes
1answer
49 views

Constructing a crown graph given an independent set

A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold: (a) The set of neighbors of vertices in $C$ is ...
3
votes
1answer
42 views

Upper bound on the number of subgraphs in a tree

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc. For example, consider the ...
1
vote
0answers
33 views

Why is converting a suffix tree to a suffix array not O(nklogk) time

Let's say that we have computed a suffix tree in O(n) time, and wish to use this to create a suffix array. According to wikipedia: A suffix tree can be built in $O(n)$ and can be converted into a ...
0
votes
0answers
39 views

Augment the tree data structure for disjoint sets to implement the PRINT operation

Consider the following new operation for disjoint sets PRINT(x): print every element in S_x the set containing x One Approach that I found but couldn't figure out completely : In addition to tree we ...
2
votes
1answer
146 views

A connected acyclic graph has $n-1$ edges

Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third: $G$ is connected $G$ is acyclic $G$ has $n-1$ edges Proving $1, 2 \implies 3$ A connected, ...
1
vote
1answer
48 views

How can I make my algorithm more efficient?

I came across an algorithmic problem. I do not know how to do it optimally. The problem is as follows: There is an increasing array $A$ of size $n_1$ There is an array $M$ of queries of size $n_2$ ...
3
votes
1answer
164 views

Changing a matrix to become an ancestry matrix

An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some ...
1
vote
0answers
20 views

Is there an official name for this tree merging algorithm?

Is there a standard name for an algorithm to handle this type of tree merge? Each node of the tree has a label. Nodes from the 2 trees should be combined if they have the same label, and their values ...
4
votes
2answers
118 views

Why does my code work: bijecting binary trees to Dyck paths

The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan ...
0
votes
1answer
125 views

How to calculate the average depth of a binary tree?

My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach ...
0
votes
1answer
78 views

Time complexity of insertion in binary search tree

Given a binary search tree $T$, we insert $n$ elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$...
0
votes
1answer
133 views

Find successor element in heap

Does finding the successor of an element in a heap take $O(\log n)$? An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?
1
vote
0answers
36 views

Weight of lowest common ancestor satisfies strong triangle inequality

How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality: $$ d(x,y) \le \max(d(x,z), d(y,z)) $$ How do I even start such a ...
0
votes
0answers
11 views

2D segment tree update/modification step complexity

I am having trouble understanding the complexity of the "Modification query" in https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/. It states at the bottom of the ...
1
vote
0answers
34 views

Count number of intervals containing a point

There is a problem (10.6) in Computational Geometry: Algorithms and Applications 2.edition by de Berg et al. where you have to solve the problem of given $n$ intervals, $I$, on the real line, count ...
1
vote
2answers
102 views

Proving that a preorder traversal of a rooted tree can be performed in linear time

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
1
vote
0answers
16 views

Better version of heavy-light decomposition: always draw path to largest subtree

Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ). The problem: given any tree of size N, find a way to split it into ...

1
2 3 4 5
15