Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
45 views

Parallel prefix sum/scan on trees

Let $T$ be a rooted, finitely branching tree, with values from $A$ in its nodes; $T(j)$ is the value of a node called $j$. $A$ is a commutative monoid. The "bottom-up scan tree" of $T$ is a ...
Patrick Nicodemus's user avatar
3 votes
0 answers
27 views

Big O of a parallel tree algorithm

Let $T$ be a finitely branching tree. I will call a subtree of $T$ a "tassel" if it is of width one, closed downward, and is maximal subject to this criterion. Equivalently, a tassel is a ...
Patrick Nicodemus's user avatar
0 votes
2 answers
137 views

Recursive formula for height of BST

Let $H(n)$ be the average height of a BST with nodes from ${1,...,n}$. I think that $$H(n) = \frac{1}{n}\sum_{i = 0}^{n-1}\left[\text{max}(H(i), H(n-1 -i)) + 1\right]$$ But I don't know how to prove ...
user167064's user avatar
2 votes
1 answer
251 views

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig. what to prove about the general "graph search": (Here I assume "within ...
zg c's user avatar
  • 59
1 vote
0 answers
36 views

Bucheim-Walker corollary for DCGs

The Bucheim-Walker algorithm is used for drawing trees. However, there are many real-world examples where Directed Cyclic Graphs would benefit from such an algorithm (e.g. family trees with ...
Sam's user avatar
  • 133
3 votes
1 answer
199 views

Time complexity of tree algorithm

I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $A$ whose input is the root of a binary tree $T$. $A$ recurses so that it's called on each and every ...
onepiece's user avatar
  • 133
1 vote
0 answers
61 views

Optimal Data structure for queries involved rectangles and cartesian coordinates

What data structure would be optimal in terms of time and space for the following usecase: Given information about rectangles in the form of- {rectangle_id,left_bottom_corner_x, ...
fat_gladiator17's user avatar
2 votes
0 answers
17 views

Canonical forms for unlabeled unrooted trees

I know an unlabeled unrooted tree normalization algorithm that uses parentheses: label each vertex with () while there are more than two leaves repeat: remove each leaf placing its label within the (...
Vor's user avatar
  • 12.5k
1 vote
0 answers
21 views

In monte-carlo tree search, do you propagate the result from the terminal or just the leaf?

In most descriptions of monte-carlo tree search, I see the simulation step described as: Play out a game from the leaf node until a terminal node is reached and get the result. And the ...
Kyle's user avatar
  • 11
1 vote
0 answers
34 views

How do I optimally fuse nodes in a tree structure?

I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
RunOrVeith's user avatar
1 vote
1 answer
47 views

Finding the pair of nodes with maximum distance in an arbitrary rooted tree

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, ...
Mason Rashford's user avatar
1 vote
1 answer
58 views

Does a sorted sequence from in-order traversal imply a binary tree is a BST?

An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the ...
Mason Rashford's user avatar
2 votes
1 answer
88 views

Optimal graph data structure for set of points that allows dynamic updates

We aim to optimize the execution of a specific task. Consider a set, P, containing N 2D points. A new query point, p1, is introduced, and the objective is to identify the nearest point in P to p1. If ...
Apurv Mishra's user avatar
0 votes
0 answers
33 views

Dynamic Program to find well formed set in a rooted tree

You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
Sooraj S's user avatar
  • 139
0 votes
0 answers
24 views

Morton-code based Linear BVH: Why do triangle's bounding boxes' centroids give higher-quality trees than triangles' centroids?

I've implemented linear BVH as described in Karras 2012, and I was using triangles' centroids for Morton Code generation. I found recent papers and implementations use triangles' bounding boxes' ...
nitroglycerine's user avatar
1 vote
2 answers
101 views

NP-hardness of modified distance-colouring of graphs

Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
r236's user avatar
  • 11
0 votes
2 answers
60 views

Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue. On the one ...
Root Groves's user avatar
0 votes
0 answers
64 views

Finding the Depth-First Index of a Child Given the Parent's Depth First Index Index in Complete k-ary Tree

I have a complete k-ary tree with a depth of $d$. If I'm given a node's depth-first index, I'd like a closed-form formula for calculating both the nodes children's depth-first indexes along with a ...
Torkoal's user avatar
  • 101
1 vote
1 answer
65 views

Efficient intersection of multiple paths in a tree

Consider a graph tree $T$, where we are given $k > 1$ unique pairs of nodes $\{u_1,v_1\}\dots \{u_k,v_k\}$. Let $P_{i}$ denote the unique path on $T$ between $u_i$ and $v_i$. Then, my problem is ...
rolfvdhulst's user avatar
-1 votes
1 answer
37 views

Uniquness of a graph. Why do we need to add e1 to B to create a cycle? [closed]

If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it'...
kjkjkjkjkj's user avatar
0 votes
1 answer
37 views

Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?

I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list. The ...
Some Name's user avatar
  • 105
0 votes
1 answer
272 views

Finding a cycle of length log(n) given min degree

Let $G = (V, E)$ be an undirected graph such that every $v\in V$ has $\deg(v) \geq 3$. We must create an algorithm that outputs a cycle of length O(log(n)) if it exists. This algorithm must return in ...
Money Mit's user avatar
0 votes
0 answers
21 views

Subtrees of decision tree for comparison sort are recurrences?

Consider sorting on $n$ distinct elements, where all $n!$ permutations are possible. I think a decision tree for comparison sort can can be uniquely characterized as $T(a,n!)$ where $a$ is the ...
C.C.'s user avatar
  • 149
0 votes
0 answers
12 views

Keeping in a list a list of recent insertions/removal to/from a list of lists

I have a list of lists T. I stress test my database software by randomly adding and removing sublists and elements of sublists to/from T and from/to my database. (After this I compare T with the ...
porton's user avatar
  • 433
0 votes
0 answers
35 views

Are pre-order, in-order and post-order the only traversals for depth-first search?

With a binary tree, the 3 approaches for the tree below are listed. ...
heretoinfinity's user avatar
0 votes
1 answer
69 views

Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
ilovewt's user avatar
  • 113
2 votes
0 answers
101 views

On definitions of graph width

Wikipedia shows graph width $k$ as the degeneracy, an ordering of the vertices $v_1,\ldots , v_k$ for which, if we orient each edge $(v_i, v_j)$ towards $i$ where $i<j$, the maximal degree is at ...
Eric_'s user avatar
  • 435
0 votes
2 answers
59 views

AVL tree with balance factor equal to depth

If you were to define an altered AVL tree where the balance factor (the difference between the height of the left and right subtree) of a node must be less than or equal to the depth of the node (in ...
Remeraze's user avatar
1 vote
1 answer
69 views

Clarifications about tree-width definition

I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here: https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb I'm finding ...
Benicio Agüero's user avatar
5 votes
0 answers
76 views

Completeness of red-black tree operations

Red-black trees are defined to have the following invariants: The nodes are in sorted order (it is a binary search tree). The root is black, and leaves are black. Every red node has black children. ...
Mario Carneiro's user avatar
0 votes
1 answer
114 views

BFS on a graph and BFS on a tree

I found the following question in my book and I have no clue on what the answer should be: What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree generate ...
Robert's user avatar
  • 1
2 votes
1 answer
102 views

Minimum spanning tree with dynamic edge cost based on degrees

I have a problem that I'm struggling to solve or even name, I'd really appreciate any help or pointer to potential existing solutions. Suppose there is a connected graph $G$ and we are trying to find ...
quanecon's user avatar
3 votes
1 answer
449 views

Maximum Independent Set of a Tree using Greedy Algorithm

I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph? ...
wamengti's user avatar
0 votes
2 answers
55 views

Does there always exist an optimal solution to the metric steiner tree problem which doesn't contain any steiner nodes?

Given an undirected graph with nonnegative edge weights and a partition of the vertex set into terminals and Steiner vertices, the Steniner tree problem consists in finding a minimum weight tree in ...
SVMteamsTool's user avatar
0 votes
1 answer
177 views

Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes

To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children. For the inductive step, consider a node $x$ that has positive height and is an ...
ihsingh2's user avatar
0 votes
1 answer
27 views

What algorithm accepts a set of strings as input and outputs a regex of minimal size?

We seek an algorithm. Inputs to the algorithm are a set of strings $A$ and the output of the algorithm $A$ is a regular expression $r$ such that: The size of regular expression $r$ is minimized. If $...
Toothpick Anemone's user avatar
0 votes
0 answers
87 views

What algorithm will convert a regex into a tree of predictable size?

How do we quantify the size of a regular expression? A problem in computer science which sometimes arises is converting a regular expression into a tree. What rules can we use to ensure that the tree ...
Toothpick Anemone's user avatar
0 votes
0 answers
57 views

Is there a cannonical name for a tree in which none of the nodes have a value attribute except for the root node?

Is there a canonical name for a tree in which none of the nodes have an attribute to store a value, or data-item, except for the root node? A primitive implementation of this data-structure is shown ...
Toothpick Anemone's user avatar
0 votes
1 answer
36 views

find maximum in arbitrary expression tree

Originally posted on SO. I have a very simple language that gets compiled to an Expression tree, and then evaluated. Users can define mathematical operations, use variables and control flow. Moreover, ...
apocalypsis's user avatar
3 votes
1 answer
116 views

Find the largest caterpillar subtree

I have a problem to solve, but I am having some issues with it... Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
aurel1510's user avatar
1 vote
1 answer
105 views

fastest algorithm to count leaf nodes (i.e. terminal nodes)

With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time? Python code - (mag(P) = number of leaf nodes of tree ...
Ten's user avatar
  • 119
0 votes
1 answer
41 views

the size of nice tree decomposition

Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation. For a ...
Jxb's user avatar
  • 318
2 votes
4 answers
151 views

Best C++ STL container to store bodies in an N-body simulation?

I am writing an N-body simulation in C++ that has to be able to deal with large N ($N \le 10^6$). Everything has been going well so far, but now that I have started to code in collisions between ...
Gregor Hartl Watters's user avatar
0 votes
0 answers
106 views

Range updates in segment trees of sorted arrays (merge sort trees)

I understand range updates in segment trees using lazy propagation where each node is an integer. Merge Sort Tree (source GFG): https://media.geeksforgeeks.org/wp-content/uploads/20220722205737/...
Yuv's user avatar
  • 139
2 votes
1 answer
129 views

Is there a name for this kind of binary tree?

While working on a math problem the following tree structure came up: o \ o / o / \ o o / \ / It is a binary tree with the ...
Anthony Garcia's user avatar
0 votes
1 answer
100 views

Set of all vertices in a directed tree that are within distance of strictly larger than 2

As the title says, I'm trying to solve the question where: Input: A directed tree $T = (V, E)$. Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u,...
Salty Champ's user avatar
0 votes
0 answers
40 views

How the depth of the vertices changes along the route in the splay tree after search

Studying for the exam in "Advanced Algorithms" course. I'm trying to solve the following question: This question discusses a search operation for a vertex ...
vesii's user avatar
  • 223
1 vote
1 answer
31 views

Optimum placement of zigzag trees in order to minimize the makespan

Suppose we have some trees of the following forms: We want to place these trees in a linear fashion in a way such that the last node has the minimum distance to the first node. For instance, if we ...
Fish_n_Chips's user avatar
1 vote
1 answer
66 views

Generate uniform random vectors

Problem : Consider a random vector $v$ which is uniformly distributed over the sample space $S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$ . How to efficiently generate such random vector ? note :...
C.C.'s user avatar
  • 149
0 votes
2 answers
114 views

How might we hash two trees?

Suppose that you had two trees. Our goal is to convert the two trees into two integers such that two trees are the same if and only if the two integers are the same. Suppose that we have a function ...
Toothpick Anemone's user avatar

1
2 3 4 5
17