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

learn more… | top users | synonyms

1
vote
2answers
21 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
33 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
173 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
29 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
61 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
161 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
45 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
37 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
31 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
31 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
37 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
31 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
72 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
74 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
40 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
42 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
49 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
189 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
89 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
53 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
39 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
84 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
126 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 ...
6
votes
3answers
729 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
204 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
59 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
61 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
54 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
59 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
46 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 ...
0
votes
1answer
105 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
90 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
63 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
41 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
61 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
98 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 ...
5
votes
0answers
66 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
4
votes
1answer
90 views

Shortest-depth routing algorithm

This problem came up in a graph network routing context, it can be expressed as follows: Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k ...
0
votes
2answers
375 views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
1
vote
1answer
55 views

Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
1
vote
1answer
253 views

Checking whether two paths are intersecting in a tree

The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint ...
3
votes
2answers
92 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
-1
votes
1answer
109 views

Number of Different AVL Tree

I studying the related question. http://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
-1
votes
1answer
189 views

Sum of all nodes from A to B in a Tree [closed]

Given a Tree and pointers to two of it's nodes A and B (a key value of each node is positive). Find an algorithm that sums up all the values on the path between A and B, when preproccessing is ...
3
votes
2answers
59 views

How do learn the most important nodes in a tree?

I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles. I am trying to build a stemmer which chops off suffuxes from each words, so ...
0
votes
2answers
60 views

Reason for differences between ways of specifying trees

Might be an odd question but how is it that when you specify a tree using an adjacency list emphasizing leafs first you state only need state 0 or 1 parent for each node but when you define a tree in ...
0
votes
1answer
68 views

Red black tree partition to $\sqrt{n}$ trees

This is a question I have stumbled upon in an old Algorithms test I found online: A) Plan an algorithm that does the following: Input: Red-Black tree Output: $\sqrt{n}$ seperate trees, so that ...
-1
votes
1answer
51 views

Find MST based upon new definition

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
-2
votes
1answer
105 views

Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity [closed]

I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I ...