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

learn more… | top users | synonyms

0
votes
1answer
30 views

undirected graph without weights and DFS [on hold]

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times. check that G is ...
0
votes
1answer
19 views

What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
-1
votes
0answers
20 views

Haskell Defining an infinite tree [on hold]

I want to define an infinite tree in Haskell using infinitree :: Tree, but want to set a pattern up for each node, defining what each node should be. The pattern is 1 more then then its parent. I am ...
0
votes
2answers
55 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
0
votes
1answer
27 views

Collecting and combining data from iterative DFS on read-only trees

I am iterating over a tree through an API. This API provides a list of nodes sorted in post order DFS. I need to gather data for each node in the tree, combine that data with the parent's data ...
0
votes
1answer
30 views

Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori

Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at ...
1
vote
2answers
43 views

BIT: Unable to understand update operation in Binary index Tree

I have just read this answer and was very satisfied and it is indeed a fantastic answer. It taught me the working of BIT. But at the end, the second last paragraph is where I am struggling. It says, ...
5
votes
2answers
121 views

Algorithm: ordering non-overlapping intervals

Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \{I_1,...,I_n\}$ and for any two $I_i, I_j \in \mathcal{I}$, we have that $I_i \cap I_j$ is trivial (that is: contains at most one ...
-1
votes
2answers
60 views

what is the advantage of using threaded trees?

Since a binary tree with $N$ nodes has $N+1$ NULL pointers (across leaves), half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a NULL left ...
0
votes
0answers
26 views

Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
0
votes
0answers
19 views

Theory basis on collection types classification?

After having a look at commonly used collections (Array, Linked List, Hash Map, Hash Set, Tree Map, Tree Set, ...), it is easy to see that almost all of that types inherently implemented using either ...
0
votes
0answers
34 views

Generalized steps to find tree traversal for any m-ary tree

So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I ...
1
vote
0answers
50 views

Enumerate subtrees of a given size in a graph

Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree? Other ...
1
vote
2answers
33 views

Calculating the number of unique BST generatable from n keys, why is my number so large

I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3) Here's my solution: In case 1, we have each node have possibility, 3, 2, 1, respectively, so 3*2*1 = 6 ways ...
1
vote
1answer
39 views

Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

My best attempt at a specific case of the problem where $n =$ 256: For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq ...
5
votes
3answers
202 views

How to choose the maximum number of nodes (with constraints) from a graph

Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$. A positive integer $x$ is given and you want to choose at ...
0
votes
1answer
30 views

Rotations in splay trees

I am having some difficulties splaying the element 4 to the root. Considering the following splay tree. 0 \ 1 \ 2 \ 3 \ 4 ...
6
votes
0answers
73 views

Is finding a weight-balanced tree NP-hard?

In the following, we are considering binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of its weighted leaves. Let $T.l$ and $T.r$ be the left child and ...
1
vote
2answers
172 views

Difference between spanning tree and a tree?

Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem ...
3
votes
1answer
56 views

Counting nodes in a trie

I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem. Question: Given a random $m$-ary trie with $n$ total leaves, letting $I$ be ...
0
votes
1answer
40 views

Vertex Cover of size k in a tree?

What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex ...
1
vote
2answers
51 views

Implementing an interval tree using arrays?

Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i ...
0
votes
1answer
33 views

Numbering levels of a tree [closed]

I find the need to use an explicit level numbering for a tree. i.e. in the tree: A / \ B B /\ /\ C C C C should I number the level C the 3rd and ...
-1
votes
1answer
65 views

Finding a maximum-diameter tree in an undirected unweighted graph

The diameter of a graph is the largest of all shortest-path distances in it. How can we find a tree of maximum diameter within an undirected unweighted graph? Note that the tree does not have to be a ...
0
votes
1answer
45 views

Solving the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$ using a recursion tree [duplicate]

I have homework from recursion tree and despite my search for hours I could not find the answer to this problem. I appreciate if you can help. Draw a recursion tree and give a tight asymptotic ...
2
votes
2answers
94 views

Is there a difference between perfect, full and complete tree?

Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?
4
votes
3answers
77 views

Is the height of the tree the number of edges or number of nodes?

I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree ...
-1
votes
1answer
52 views

Min/max height of B-tree

I have a question asking for the minimum and maximum height $h$ of a B-Tree with 1000 elements under following conditions: each block can save 1 to 4 records, the number of internal nodes is ...
0
votes
0answers
65 views

Remove atmost K subtrees

Given a tree with N vertices numbered from 1 to N. The vertex 1 is the root of the tree. Each vertex is assigned with an integer weight. A remove operation can remove sub-tree rooted at an arbitrary ...
2
votes
2answers
61 views

Finding paths of certain length in trees

In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length? For example given a tree graph: ...
3
votes
1answer
234 views

Algorithm to determine whether a given graph is a caterpillar tree

I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree. A caterpillar tree is a tree that has a path to which ...
3
votes
1answer
92 views

Finding the minimum number of calls in a tree

I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before. Suppose you ...
1
vote
1answer
54 views

What is the name of this function of a tree?

I've written a recursive function of a tree, and I would like to know what it's called! It's not quite the same as the height or the width of a tree, but it seems kind of like a width. Assuming the ...
1
vote
1answer
61 views

Smallest(k) in red-black tree. How is it O(logn)?

Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1). Even if we are wanting it to find the 'k-th' smallest key in the red-black tree. ...
1
vote
1answer
86 views

How can one search in O(log n) time in a red-black tree?

How does the search operation for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ ...
2
votes
1answer
187 views

Algorithm for maximum independent set in trees

While studying the dynamic programing algorithm for the maximum independent set problem in trees I thought about the following simple alternative algorithm. I tried to prove it's correctness but I do ...
7
votes
3answers
941 views

When are binary trees better than hashtables in real world applications?

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how ...
3
votes
2answers
219 views

How many structurally different trees can be formed with n nodes?

Is there any exact formula for finding number of structurally different unlabeled trees can be formed with $n$ nodes? I searched a lot and I found some approximation formulas, e.g. here.
1
vote
0answers
65 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
1
vote
1answer
63 views

Determining on whether topology is a tree or a hypercube

Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to ...
3
votes
1answer
61 views

Data structure for counting bits set on a table

I have a table that contains only bits. I would like to be able to do the following two queries: SET any bit to 0 or 1; GET the number of bits that are set to 1 from the beginning of the table up to ...
-2
votes
1answer
41 views

Inequality to be disproved

Suppose that a search for a key in a binary search tree ends up in a leaf. Consider three sets : A,the keys to the left of the search path B,the keys on the search path C, the keys to the right of the ...
1
vote
2answers
61 views

For each vertex of a tree count vertices closer than a specified value

We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that ...
0
votes
1answer
53 views

Propagating node labels upwards in a tree

I am trying to think of an efficient way to synchronize a tree's nodes with the following rules. Consider for instance this tree: so the top of the heap is always ...
1
vote
1answer
161 views

Binary tree traversals reversed

Am I correct in saying that traverse(node): if node is null, return print node traverse(node's right subtree) traverse(node's left subtree) would ...
2
votes
1answer
118 views

Check whether it is possible to turn one BST into another using only right-rotations

Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, ...
0
votes
2answers
66 views

Can we construct a binary tree with width and height Θ(n)?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
43 views

Implementing BTrees without pointers

I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in ...
2
votes
1answer
75 views

How append, prepend, and generally insertAt work in RRB-tree

I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient ...
0
votes
1answer
163 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 ...