# Questions tagged [trees]

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

579 questions
Filter by
Sorted by
Tagged with
365 views

### What is a Huffman tree for a Block-Code?

We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ". I have created a Huffman tree for the string w. We get the following table: Now I want to create a Huffman tree for a Block-Code ...
112 views

### Given a digraph and a root, find a tree that minimizes the sum of edges

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$. Solution: A directed tree with root $v$. Objective: Minimize total weight. My formulation: ...
104 views

### What is a good metric to choose the degree of a B-Tree?

What is a good metric to pick the degree of a B-Tree? I assume this depends on the number of expected elements? Degree 2 gives us a 2-3-4 tree (each node contains 1-3 items and 2-4 children). How can ...
115 views

### optimal lifted phylogenetic alignment - how to improve time complexity?

optimal lifted alignment - is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$). The algorithm then assigns strings to the ...
170 views

### Merging two binary search tress

You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$ nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys in tree B. ...
886 views

### weight balanced binary tree vs height balanced binary tree [closed]

What are advantages and disadvantages of weight balanced binary tree over the height balanced binary tree?
837 views

### Merging two complete heaps

Suppose you have two heaps each containing $2^k - 1$ elements. Design an efficient algorithm for merging these two heaps into a single heap. My approach was to assume two heaps are maxheap. Create ...
466 views

### Minimum cost edge in path between nodes (tree)

I'm working on a problem and I've managed to design an efficient algorithm, but I'm stuck at the last part. After some processing I'm left with a tree and I have to answer several queries of the ...
188 views

### Is there a Tree with deterministic traversal, but which nodes can vary?

I have a dynamic closest-pair problem. In my problem though, the points never move, but instead disappear and reappear. That is, I would like to find for a point $p$ (where $p\in\mathbb{R}^3$)* in a ...
138 views

### Assignment of coprime values to a tree

I recently saw this question somewhere and thought a lot on it but was unable to find an efficient solution for it. Asked on Stack Overflow but got no solution there. The Problem is as follows - ...
1k views

### What is the Big-Oh asymptotic complexity of learning in Random Forests?

Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right. CART (Classification and Regression Trees) uses the Gini index for ...
378 views

### Expected distance between tree nodes

I have been given a tree with n nodes and n-1 edges with it's weight. There are two people A and B. I have been given a list of nodes of size k. A will pick a random node x from this list and B will ...
60 views

### Tree - how much elements have the subtree got?

It's the continuation of the exercise: https://cs.stackexchange.com/questions/65384/tree-elements-influence-on-another-elements-searching-for-specific-elements I need to say how many elements do I ...
106 views

### Expected distance between two random nodes in weighted tree [duplicate]

Given an undirected connected graph with N nodes and N-1 edges. Out of N nodes, 1...k nodes are selected, out of which 2 nodes are selected randomly (uniformly). How do I calculate the expected ...
151 views

### Assigning all nodes in a tree a parent and children

If one was given a tree in the form of a list of $A,B$ (not implying which one is the parent) pairs implying that node $A$ and $B$ were connected by an edge, how could a root node be determined and ...
123 views

### Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
610 views

### What is the “Chairman Tree”?

My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs ...
1k views

### Why do so many 8-Puzzle solving algorithms use DFS instead of BFS?

I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the ...
145 views

### What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
179 views

### What makes is the difference between a tree and a graph?

I have seen in some text books that they have started talking about a tree and then they use the terms such as vertices and edges and treat is as a graph. What makes a graph a graph and what makes a ...
153 views

### Making mathematical expressions as balanced trees as possible

I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible. This is what I have done so far, but is there a way to make them even more ...
141 views

### Algorithm to compare hierarchical data

The task is to compare two trees and determine what are the changes. Both trees are represented as an adjacency list (ID, ParentID). Base tree: A (ID: 1, ParentID: 1) B1 (ID: 2, ParentID: 1) C1 (...
140 views

### Data structure for a Rete in production rule system

Example of Data This is the data for one monkey. There are many similar but different monkeys. ...
85 views

### What is the error when using Levenshtein distance on flattened binary trees?

I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive. The trees are stored as a flattened list of indices into node and terminal ...
233 views

### Fenwick Tree Traversal using Binary value of Index

Can someone explain me how do I execute sum query from Index 0 to Index I given the binary value of that Index I. There are some trivial question that I want to know : Do we have to remove last set ...
3k views

### Why is the running time for BFS $O(b^{d+1})$?

In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as ...
523 views

### Ternary decision tree for the lower bound of comparison sort with 3-way comparisons

All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook) Now what if each comparison yields strictly 3 outcomes, i.e. ...
114 views

### Creating a decision tree?

So I'm trying to split on an attribute "Color" that has possible values (Blue,Green,Red,Orange,Pink). I'm splitting on entropy values, and the best split can either be Multi-Way 5, Multi-Way 4, ...
309 views

### Can a shortest-path tree be a also maximum spanning tree?

If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example! I ...
432 views

### Relationship between height and depth of a binary tree

The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree. The following binary tree is full according to ...
197 views

### Comparison of Decision Trees: RTED vs MLE

I read two papers discussing how to compare between decision trees. One of them is RTED (that is specifically for trees and sub-case is decision trees) can be found here (RTED: A Robust Algorithm for ...
1k views

### Extract Tree from multi-edge undirected graph

I have the following multi-edge, undirected graph. I would like to extract the following tree from it, if I start from the node $A$. Do you know of any algorithm that I can use to achieve that ? ...
18k views

### What is the difference between radix trees and Patricia tries?

I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a ...
194 views

### Get mathematical relation of node IDs of a subtree based on a given tree

(I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.) Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning ...
46 views

### Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$

Let's consider a rooted tree $T$ of $n$ nodes. For any node $u$ of the tree, define $L(u,d)$ to be the list of descendants of $u$ that are distance $d$ away from $u$. Let $|L(u,d)|$ denote the number ...
97 views

### Why the update low value in Tarjan's for the ancestors is not it's low value instead of it's discovery value? [closed]

In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this ...
262 views

### Distance query in trees with integer edge weights (Constant time, linear space)

Consider an unrooted tree with integer edge weights. I'm looking for a linear space data structure which allows for constant time distance queries (finding the distance, i.e. the sum of edge weights, ...
661 views

### what is the name for the space between the leaves of a tree

I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree. In number theory (a part of math) this is known as a topograph does it have a name in CS?
157 views

### AVL Tree Height

What is the height of an AVL Tree? I keep finding contradicting definitions. I found these two on wiki: Height of node: The height of a node is the number of edges on the longest path between that ...
52 views

### FInding number of ancestors at given depth

I have a rooted tree with $n$ vertices. I want to be able to answer the given queries in logarithmic time after setting up some sort of data structure (preferably in time $n\log n$. The query is ...
21k views

### Time complexity of Depth First Search [closed]

Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about. I ...
285 views

### What are the differences between parse and decision trees?

I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully. I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a ...
33 views

### Unsure about parse tree of PCFG

I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa. My solution would look like ...
50 views

### Are results after performing operations on AVL trees ambiguous?

After performing operations (e.g. insertion/deletion of a node - rotations) on an AVL tree, is the result fully determined by the order of insertion on the initial tree, or do multiple solutions ...
745 views

### Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
3k views

### Constructing binary search tree from given data

The data are in alphabets. U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A. Perform pre, in and post order traversals. I'm confused as how to construct it in the 1st place. Only sense i ...
81 views

### Are there data structures that mix a tree structure with lists?

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data. Something like this (I'll be ...
258 views

### Large non-array data structure to describe order of elements

I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph ...
I'm looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$ Output: the maximum-cost subtree containing $\le k$ edges ...