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
16 views

Job Interview Question

Consider the following (Job Interview) question: As a programmer for Zoom company suggest an algorithm that satisfies the following complexity requirements for the given functions: In the following ...
0
votes
0answers
16 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: ...
-1
votes
0answers
32 views

Recurrence relation $T(n/10) + T(c·n) + n$

Given the following question: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure) ...
0
votes
0answers
36 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
1answer
32 views

What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of ...
3
votes
4answers
4k views

Depth of any node x in Weighted Quick-Union Algorithm

I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall ...
1
vote
0answers
25 views

Finding differences and similarities between tree graphs

Are there any known techniques for "diffing" trees, such as phylogenetic trees?
1
vote
1answer
37 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
8 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 : ...
0
votes
1answer
114 views

How to build tree from graph with specific property

We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written. We need to build tree such that for each node $i$, all nodes in the ...
0
votes
1answer
52 views

Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?

I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree. The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input ...
0
votes
1answer
198 views

Leaf nodes of B+ Tree

I have a b+ tree and i want to find the record associated with a specific key Ki. So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
0
votes
1answer
61 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
0
votes
1answer
260 views

Determine minimum and maximum number of leaves on a complete tree

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$. I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
1
vote
1answer
25 views

Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key). In general ...
4
votes
1answer
37 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 ...
3
votes
1answer
112 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 ...
0
votes
1answer
81 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 ...
0
votes
0answers
26 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 ...
1
vote
1answer
248 views

Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
4
votes
2answers
73 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 ...
4
votes
1answer
61 views

How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
0
votes
1answer
206 views

Merge nodes in a graph to form a tree

I have an undirected graph which may have 2 edges that connect the same pair of nodes. A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a ...
0
votes
0answers
22 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 ...
1
vote
1answer
354 views

Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
1
vote
1answer
28 views

Understanding recursion tree for withdrawal formula

$$ T(n) = T(n-a) + T(a) + cn $$ Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$ And I don't understand why. Maybe I didn't understand the ...
1
vote
3answers
181 views

Minimum-average-cost subtree that is not necessarily spanning

I'm looking for an efficient algorithm for the following problem: Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root)....
0
votes
2answers
26 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
57 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? ...
1
vote
1answer
1k views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
0
votes
0answers
12 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 ...
0
votes
1answer
25 views

Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
7
votes
3answers
476 views

What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree ...
3
votes
1answer
119 views

Is this data structure a hypertree or they are just isomorphic trees?

I have a data structure described as following: - It's a collection of trees. - Each tree has the same structure. - Each tree has information of diferent nature. ...
0
votes
0answers
15 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
38 views

Tree search returning parents and children

I've a flat structure where a node references its parent instead of children class Node(int Id, Node Parent, string Data); Given a list of all nodes, and a ...
0
votes
1answer
34 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 ...
1
vote
2answers
8k views

Order of a leaf node in B+ Tree

Going with the definition, that order of a B+ tree is the maximum number of children a node can have. What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node ...
5
votes
2answers
142 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
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 ...
16
votes
3answers
14k views

Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
0
votes
1answer
77 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 ...
1
vote
1answer
45 views

How to generate tree variants of a tree using recursion?

I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion? any help is ...
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
24 views

Computing childrens of ith node of a d-ary tree

Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n). The formula for indices of children of node no. i is given as: {(1-i)d+2, ... , min{n,(1-i)d+d+1}...
2
votes
1answer
653 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
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
2 3 4 5
14