# Questions tagged [trees]

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

865 questions
Filter by
Sorted by
Tagged with
24 views

### Trie minimization when order doesn't matter

How would I ensure I obtain a minimal trie when the order of elements is not important (ie - "abdc" is equivalent to "cbad" for my purposes)? To be clear, minimal means the least ...
24 views

### I don't understand the reason behind O(h) time complexity in this MIT OCW Algorithms question

I faced the following question in a problem session: Gal Ore is a scientist who studies climate. As part of her research, she often needs to query the maximum temperature the earth has observed within ...
26 views

### Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G ...
1 vote
51 views

### Efficient data structure for fast Insertions, lookups, and union operations on sets

I need data structure that is able to perform the following operations efficiently: Insert a new element into a set. Lookup element in set. Compute the union of two sets. Union operation should ...
59 views

### Possible values of root of AVL tree

I have a question: given that an AVL tree holds numbers 1, 2, 3, ..., 1000, what are the smallest and largest possible values of the root? I have a feeling it is 500 and 501, but I don't know how to ...
• 21
25 views

### How to do different cases of Union Find?

Here is the question: I understand that the absolute parents are 1, 3, 0, and 8, respectively, but I'm not sure how to do union here. Could someone help me understand how to do this?
49 views

### The Hydra Game runs forever

I saw this question here: The Hydra Game algorithm I am also running into troubles with the same problem. I also learned of the problem in this Numberphile video, and also tried to compute it myself. ...
• 1
1 vote
28 views

### Minimum number of vertices in a tree with pathwidth $h$?

Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$. I'm guessing this is a fairly easy question. We know that a complete binary ...
512 views

### How to represent BFS and DFS between adjacency matrix and list?

I'm trying to figure out how to best represent BFS (Breadth First Search) and DFS (Depth First Search) on a graph, specifically between being represented as an adjacency matrix and an adjacency list. ...
1 vote
48 views

### Tree node indexing

I'd appreciate any solutions, ideas, or pointers to relevant literature. I'm attempting to design a system with nodes (representing the state of some tasks) organised in a tree structure. I'd like to ...
125 views

### Tree algorithm - arrange integer array numbers to form largest number

I have solved leetcode's Largest Number. I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
• 123
40 views

281 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 ...
• 203
1 vote
38 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 ...
• 133
359 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 ...
• 133
1 vote
71 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, ...
• 11
20 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 (...
• 12.6k
1 vote
23 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 ...
• 11
1 vote
39 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, ...
• 239
1 vote
64 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)$, ...
1 vote
71 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 ...
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 ...
34 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 ...
• 139
39 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
116 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 ...
• 11
63 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 ...
68 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 ...
• 101
1 vote
90 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 ...
41 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'...
40 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 ...
• 105
359 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 ...
27 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 ...
• 159
13 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 ...
• 493
36 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. ...
79 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 <...
• 113
102 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 ...
• 455
66 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 ...
83 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 ...
80 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. ...
174 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 ...
106 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 ...
• 21
774 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? ...
• 31