Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
972 views

Notation Conventions for Tree Data Structures

I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to ...
1
vote
1answer
3k views

Calculating traversal position of a node in a full binary tree, given its path

Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in ...
3
votes
1answer
121 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. ...
2
votes
1answer
3k views

Why does a suffix tree have a linear number of nodes (relative to input string size)?

Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.
10
votes
3answers
48k views

Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

In my Java class, we are learning about complexity of different types of collections. Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
3
votes
1answer
163 views

Constructing a tree from disjoint graphs

I will preface my question with the definition of a simple tree that applies to my question: A simple tree is an undirected and connected graph with no cycles. I am having difficulty coming up ...
3
votes
1answer
399 views

Size of the universe for van Emde Boas Trees

In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde ...
5
votes
1answer
1k views

Explanation of recursive structure of Van Emde Boas Tree

From Van Emde Boas trees lecture: We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of a bit vector, but shrink the universe size recursively by a square root at each ...
8
votes
3answers
1k views

Finding the height of all nodes in a forest

I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges ...
7
votes
2answers
1k views

Separate all leaves of a weighted tree with minimum weight cuts

This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete ...
15
votes
1answer
419 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
1answer
381 views

What is postorder traversal on this simple tree?

Given the following tree: Which traversal method would give as result the following output: CDBEA? The answer in my study guide is Postorder, but I think postorder would output: DEBCA. Am I wrong?
4
votes
2answers
516 views

Counting trees (order matters)

As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In ...
8
votes
1answer
1k views

What use are the minimum values on minimax trees?

Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning): When marking the the tree with $[\min,\max]$ values bottom-up, we first traverse node $3$ ...
20
votes
5answers
553 views

Efficient compression of unlabeled trees

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...
10
votes
3answers
4k views

Algorithm to test whether a binary tree is a search tree and count complete branches

I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) ...

1
11 12 13 14
15