Questions tagged [trees]

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

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

How to find diffrenet ways to implement merge and delete_min operation in binomial heap?

I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says: ...
0
votes
1answer
32 views

2-3 tree: Sum of leaves in a given range

I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which ...
1
vote
1answer
44 views

What is the Number of epochs with no improvement after which training will be stopped.?

I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check ...
0
votes
1answer
26 views

How does CNN deal with rotation invariant pictures?

I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply ...
4
votes
2answers
60 views

How to make efficient path minimum queries in a tree?

Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them? My ...
1
vote
1answer
24 views

minimum number of edges that should be added to an undirected graph to make it a tree

Basically, it's this rosalind problem. You're given a number of nodes and an adjacency list. My initial guess was that the answer was the number of connected components minus 1, since by joining every ...
0
votes
0answers
27 views

Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?

Given a binary search tree(can have any height) .Some nodes its value changed and violate bst property how we can recover binary search tree property in-place by just swapping a node with its ...
0
votes
1answer
42 views

Two definitions of Safe Edge

I ran into an interview two days ago and came across one strange definition of safe edge. We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is ...
6
votes
1answer
169 views

Finding n farthest leaves in a tree

Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function: $$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$ ...
1
vote
1answer
46 views

Finding largest disjoint subtrees spanning nodes

I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found. Now for each department, I would ...
1
vote
1answer
51 views

facts on tree and MST

We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST. The following ...
0
votes
1answer
20 views

How to (Efficiently) Sort a List of Items with Parent/Child Relationship

I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member ...
1
vote
2answers
40 views

How to index a tree to allow efficient search for paths?

By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be ...
0
votes
1answer
24 views

Height of a 2-3-4 tree

Consider the following 2-3-4 tree. Does this have a height of 3 or 2 ? If I count from the external nodes ie. the ones with the square boxes then height should be 3. Not sure if they are to be ...
0
votes
1answer
35 views

How to prove that insert complexity in binary search tree is minimum O(log n)?

Is it connected to BST search O(log n) or height log n? How to prove that insert will give give you correct BST in minimum O(log n) time?
1
vote
0answers
29 views

efficient DELETE in proto-Van Emde Boas Tree?

TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know ...
0
votes
0answers
27 views

Given two 2-3 trees I would like to merge them in $O(n_1+n_2)$

Given two 2-3 trees I would like to merge them in $O(n_1+n_2)$ I've solved before that if I get an ordered list then I can turn it into 2-3 tree in $O(n)$. My questions is how can I turn two trees ...
2
votes
1answer
85 views

Number of nodes at given depth in binary tree

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction ...
0
votes
0answers
30 views

Creating Priority Search Tree bottom up from a Complete Binary Search tree in O(n)

I have a Complete Binary Search Tree of points ordered(sorted) on the y-axis (such that the point with the mid y of all the points is the root and its left children have decreasing y from the root and ...
0
votes
0answers
25 views

For every node of a tree, find the nearest ancestor node such that val[node] is coprime to val[ancestor]

Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note ...
1
vote
1answer
29 views

Should i work with tree representation as an array of nodes and an array of edges

Here is the problem, i have a graphical component that displays a tree. It takes as input an array of nodes and array of edges(eg:an edge has a source and target). I will be performing complex tasks, ...
2
votes
1answer
152 views

Bellman Ford facts and specific question

The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following: $d(v)>d(u)+w(u,v)$ holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)...
0
votes
1answer
46 views

MST and some facts via an example

$M$ is an MST of the Weighted Graph - $GR$. Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}. Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}. If $e$ is a edge ...
0
votes
0answers
26 views

data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations

I've got this question from an exercise and i'm not sure if it is possible to do so Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure ...
0
votes
1answer
132 views

Analysis of updating vertex and one example?

I see the following image on google: And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
0
votes
0answers
13 views

Fast but simple fully persistent trie

I need fast (not worse than about log of the sum of maximum number of nodes and the maximum number of subnodes per node) and fully persistent trie. I need an easy (quick to code) implementation. The ...
0
votes
0answers
21 views

Trying to convert algorithm from recursive to iterative

I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums: ...
0
votes
0answers
45 views

Prove that $T(n)=\omega(n)$?

Edit: can someone provide clear answer with all details Given: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
1
vote
0answers
26 views

Finding differences and similarities between tree graphs

Are there any known techniques for "diffing" trees, such as phylogenetic trees?
1
vote
1answer
44 views

How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$

I try to find tree height such that first i define: $H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$ then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree ...
0
votes
0answers
9 views

tool to insert nodes in a tree with queries

I have a tree where each node has a type. Multiple nodes can have the same type. I want to insert new nodes in this tree at some specific positions specified by queries, such as : ...
5
votes
1answer
43 views

BVH construction without sorting

Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives ...
0
votes
0answers
27 views

sum selected nodes of a set in $\log n$ time

Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation ...
4
votes
2answers
75 views

Can Edge Belong to a cycle if it is part of multiple BFS products

Given a simple connected undirected graph. with V vertices and E edges. Let e be some edge from E. If I perform |V| different BFS runs - meaning started each time from a different vertex - and in ...
0
votes
0answers
28 views

LOUDS Succinct Tree Representation

I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
0
votes
2answers
27 views

Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an "Example of a heap storing 13 entries with integer keys. The last ...
2
votes
1answer
63 views

What does it mean that B-tree leaves carry no information?

According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.". What does it mean that they carry no information? ...
0
votes
0answers
14 views

How do you prove that this tree path calculation function works, from first principles mathematically?

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
0
votes
0answers
58 views

Are some algorithms inherently recursive?

Are some algorithms inherently recursive? As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise. I am asking because I struggled to ...
4
votes
1answer
116 views

How to detect “tree-able” set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
1
vote
1answer
218 views

Why does the formula floor((i-1)/2) find the parent node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with parent ...
1
vote
1answer
29 views
0
votes
0answers
19 views

How to convert recursive language grammar tree into automaton for optimal parsing?

So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees. ...
0
votes
1answer
73 views

What is a dominator node and a dominator tree?

I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node: a node d dominates a node n if every path from the entry node to n must go ...
0
votes
0answers
13 views

Derivation tree and Productions from left most derivation of string

How can one find Derivation tree and Productions of a Grammar from left-most derivation and string used? I was given input string x = abaccacaa , left most derivation lder(x)=(1,2,1,3,4,1,3,5) and two ...
5
votes
2answers
143 views

Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?

The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
0
votes
1answer
123 views

Given two identical DOM trees find same node in tree B

So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'. I can solve it in two ways - Start at the given element and traverse up to ...
3
votes
0answers
56 views

Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
0
votes
1answer
25 views

Basic Binary search tree query

Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
1
vote
0answers
23 views

Recording a histogram in a tree exhibits strange best case

The task is to record a histogram from a streaming data source. One data point is, say, a 16 bit integer. The maximum multiple of one data point before the stream ends, is < 2^32. The main ...

1
2 3 4 5
15