# Questions tagged [trees]

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

839 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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' ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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'...
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 ...
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 ...
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 ...
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 ...
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. ...
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 <...
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 ...
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 ...
1 vote
61 views

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 ...
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. ...
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 ...
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 ...
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? ...
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 ...
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 ...
26 views

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 ...
1 vote
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 ...
1 vote
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 :...
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 ...
1 vote
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?
1 vote
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 ...
1 vote
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 ...