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

learn more… | top users | synonyms

2
votes
1answer
25 views

Correctness proof for finding weighted maximum independent set for a tree

The maximum weighted independent set for a tree can found out using the following dynamic programming approach. Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } ...
-1
votes
0answers
13 views

Understanding Postorder Traversal [duplicate]

My best guess is that the post order traversal of this tree would be: B J D N P M K R W Y T Q Would anyone mind telling me if this is incorrect? Thank you in advance.
-3
votes
0answers
15 views

Post Order Analysis (Quick Check) [closed]

Left subtree, right subtree, then root. This is my understanding B J D N P M K R W Y T Q Is this correct?
2
votes
1answer
57 views

Shortest paths in weighted graphs, and minimum spanning trees

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
4
votes
2answers
92 views

MST with half the edges the maximum weight

I have been cracking my head over the following question - You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with ...
2
votes
1answer
75 views

Lowest Common Ancestor from children up?

I've seen algorithms for finding the lowest common ancestor from the root of a tree. However, I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom ...
2
votes
1answer
38 views

Guessing the structure of a finger tree from the number of elements

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger ...
0
votes
1answer
14 views

Number of path with given length within an unrooted Tree

Given a Tree (without a root) function w : v -> N and a number C - How can we count the number of verticies with distance between them equal to C. I was thinking about some smart vertice numbering so ...
0
votes
0answers
64 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
2
votes
1answer
121 views

Correctness of splitting an undirected tree into a forest of trees with even number of children

Given an undirected tree (i.e. a tree without any designated root) of even number of nodes. The task is to remove as many edges from the tree as possible to obtain a forest of trees, where each such ...
3
votes
0answers
43 views

How to apply path compression to Multi-Bit Trie

Reading a bit about the subject of Multi-Bit tries and IP matching in: High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33 Network Routing: Algorithms, Protocols, and ...
-4
votes
2answers
55 views

Rearranging linear tree with right rotates [closed]

I ran into a fun interview question, yesterday. Can anyone help me? Suppose a binary tree with six nodes is given, such that each node has only a left child. With how many "right rotate" ...
3
votes
1answer
70 views

Is a “tree” with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?

For the following $2$ cases: (1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all) (2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$) Are they considered a valid tree? It seems ...
2
votes
1answer
94 views

Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes ...
0
votes
2answers
14 views

Assistance with Notation in the Paper Entitled: “Search Through Systematic Set Enumeration”

So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free. I'm having a problem with the notation in the following definition presented bellow: ...
0
votes
1answer
39 views

undirected graph without weights and DFS [closed]

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
20 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? ...
3
votes
2answers
65 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 ...
-1
votes
1answer
36 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
48 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
59 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
140 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
71 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
22 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
43 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
52 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
39 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
45 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
242 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
31 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 ...
7
votes
0answers
76 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
178 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
81 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
43 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 ...
0
votes
1answer
34 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
94 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
47 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
135 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
83 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
58 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
85 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
71 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
257 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
93 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
57 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
80 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
89 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
262 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
1k 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 ...