# Questions tagged [trees]

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

716 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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. ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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" ...
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?
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 ...
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$ ...
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.) \$...
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) ...