Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Mapping relationtional data to hierarchical data (JSON, XML, etc.)

I'm working on a project that involves mapping relational data to a tree hierarchy. The hierarchical data is preferred to be JSON or XML. Is there an existing general algorithm for this? Current ...
slidingcurtain's user avatar
0 votes
0 answers
31 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
9 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
88 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
41 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
61 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
41 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
0 votes
1 answer
31 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
30 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
226 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
20 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
  • 129
0 votes
0 answers
11 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
33 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
0 answers
40 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
99 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
56 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
61 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
75 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
75 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
96 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
353 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
49 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
156 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
26 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
63 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
55 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
34 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
111 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
81 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
37 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
143 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
88 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
125 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
0 answers
34 views

What type of tree traversal should be performed to obtain the same splay tree?

I'm trying to figure the following: Given splay tree number 1. Perform a tree traversal on it and insert each node into splay tree number 2 in that order. What type of tree traversal should be ...
vesii's user avatar
  • 223
0 votes
1 answer
93 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
30 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
65 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
  • 129
0 votes
2 answers
103 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 vote
2 answers
192 views

Why would we want to convert a forest or generic tree to binary tree?

Why sometimes we would want to convert generic trees or forests into a binary tree? And what's the main principle behind this convertion?
Sepehr Golestanian's user avatar
1 vote
0 answers
70 views

Find maximum number of vertex-disjoint paths of length $k$ in a tree with no restrictions for the paths

I am working currently on Path-Packing problems and found this Book: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf My question is about exercise 23b on page 184. Here is ...
Mark Hase's user avatar
1 vote
1 answer
38 views

Visualising pseudo-tree with two parents per node

I have an algorithm that recursively connects together pairs of nodes into new nodes. It looks like the Huffman code algorithm, except that a node can be re-used after it has been part of a merge. The ...
Mew's user avatar
  • 141
2 votes
1 answer
471 views

Comparing two rooted n-ary trees irrespective of the order of children nodes?

I want to compare two trees: I will consider the trees equal if they are: Isomeric-i.e have the same structure. Nodes in both trees have the same values but the order of the children nodes are not ...
African_king's user avatar
1 vote
1 answer
38 views

Enumeration of tree vertices such that each vertex has unique neighbor appearing before it

(Diestel, Graph Theory) Corollary 1.5.2: Every tree has an enumeration of the vertices $\{v_1, v_2\ldots v_n\}$ such that each vertex $v_i$, with $i\geq 2$, has a unique neighbour in $\{v_1, v_2\...
Archimedesprinciple's user avatar
0 votes
1 answer
48 views

Choosing root for maximum matching in tree

This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
muser's user avatar
  • 140
1 vote
1 answer
62 views

Showing that all gomory hu trees of $K_{3,3}$ are stars with 5 edges

My lecture notes for gomory-hu trees says that it's easy to see that every GHT of the utility graph $K_{3,3}$ is a star with 5 edges. Is there any easy way to see this without manually computing every ...
SVMteamsTool's user avatar
2 votes
0 answers
69 views

Questions about the Dancing Tree data structure

I would be very grateful if someone can clarify a little bit about the Dancing tree data structure that the Reiser4 filesystem uses. It's a presentation topic that I picked, however, there seems to be ...
Huy Đỗ Nguyễn An's user avatar
0 votes
1 answer
50 views

BSTs with repeating keys

The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4. We could try an ...
prototycoon2's user avatar
0 votes
0 answers
60 views

Finding the diameter of a N-ary tree graph, without using BFS

As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph. This must be done in linear time. The problem states that the graph is undirected ...
Aishgadol's user avatar
  • 315
5 votes
1 answer
111 views

Equivallent characterization of trees?

I am a teacher of undergrad graph theory and we tend to invent some weird (and false) characterizations of trees and recently I stumbled upon this one. Is the following true? $G$ is a tree if and only ...
Michal Dvořák's user avatar

1
2 3 4 5
17