Skip to main content

Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
Sprite123's user avatar
0 votes
0 answers
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 ...
Arham Zahid's user avatar
0 votes
1 answer
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 ...
user438409385's user avatar
1 vote
1 answer
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 ...
Euler-Maskerony's user avatar
2 votes
1 answer
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 ...
HBH's user avatar
  • 21
0 votes
1 answer
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?
MotherHorse's user avatar
-2 votes
1 answer
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. ...
Lee's user avatar
  • 1
1 vote
0 answers
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 ...
Harry Vinall-Smeeth's user avatar
4 votes
2 answers
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. ...
MotherHorse's user avatar
1 vote
0 answers
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 ...
user22476690's user avatar
2 votes
1 answer
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 ...
ccot's user avatar
  • 123
0 votes
1 answer
40 views

An "edge-spanning-tree" of minimum height

Given any connected undirected graph, we can convert it into a tree by "detaching" some edges from one of their endpoints. For example, consider the graph with the following edges: $$ (1) ~~~...
Erel Segal-Halevi's user avatar
1 vote
1 answer
76 views

How to find largest caterpillar in a tree

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, ...
Stephen's user avatar
  • 11
1 vote
1 answer
30 views

Proving that Breadth-First Search (BFS) results in a bipartition of a tree

In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that ...
Ferran Gonzalez's user avatar
5 votes
3 answers
1k views

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met: Upon removing any arbitrary node, the total weight of nodes in each ...
Ferran Gonzalez's user avatar
0 votes
1 answer
21 views

Unique Tree using Inorder & Postorder traversals

This question appeared in my data structures examination : You are given that GDCBFAHEJ is an in-order traversal and GCDBHJAEF is a post-order traversal. Either build the unique tree for which these ...
Priyansh Kumar's user avatar
3 votes
1 answer
59 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
29 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
143 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
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 ...
An5Drama's user avatar
  • 203
1 vote
0 answers
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 ...
Sam's user avatar
  • 133
3 votes
1 answer
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 ...
onepiece's user avatar
  • 133
1 vote
0 answers
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, ...
zero_day's user avatar
2 votes
0 answers
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 (...
Vor's user avatar
  • 12.6k
1 vote
0 answers
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 ...
Kyle's user avatar
  • 11
1 vote
0 answers
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, ...
RunOrVeith's user avatar
1 vote
1 answer
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)$, ...
Mason Rashford's user avatar
1 vote
1 answer
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 ...
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
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 ...
Sooraj S's user avatar
  • 139
0 votes
0 answers
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' ...
nitroglycerine's user avatar
1 vote
2 answers
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 ...
r236's user avatar
  • 11
0 votes
2 answers
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 ...
Root Groves's user avatar
0 votes
0 answers
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 ...
Torkoal's user avatar
  • 101
1 vote
1 answer
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 ...
rolfvdhulst's user avatar
-1 votes
1 answer
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'...
kjkjkjkjkj's user avatar
0 votes
1 answer
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 ...
Some Name's user avatar
  • 105
0 votes
1 answer
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 ...
Money Mit's user avatar
0 votes
0 answers
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 ...
C.C.'s user avatar
  • 159
0 votes
0 answers
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 ...
porton's user avatar
  • 493
0 votes
0 answers
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. ...
heretoinfinity's user avatar
0 votes
1 answer
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 <...
ilovewt's user avatar
  • 113
2 votes
0 answers
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 ...
Eric_'s user avatar
  • 455
0 votes
2 answers
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 ...
Remeraze's user avatar
2 votes
1 answer
83 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
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. ...
Mario Carneiro's user avatar
0 votes
1 answer
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 ...
Robert's user avatar
  • 1
2 votes
1 answer
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 ...
quanecon's user avatar
3 votes
1 answer
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? ...
wamengti's user avatar
0 votes
2 answers
67 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

1
2 3 4 5
18