# Questions tagged [trees]

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

598 questions
Filter by
Sorted by
Tagged with
33k views

### BIT: What is the intuition behind a binary indexed tree and how was it thought about?

A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
48k views

### Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
1k views

### Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
20k 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 ...
42k views

### Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
487 views

43k 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 ...
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) ...
117 views

### What is the chance that this code terminates?

I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit). Intuitively you'd think it terminates, since at ...
2k views

### What are the applications of Rose trees?

I recently found out about the Rose tree data structure, but just going off of a Haskell data definition and the tiny Wikipedia description of it, I've got some ...
2k views

### Huffman tree and maximum depth

Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?
8k views

### Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?
988 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 ...
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$ ...
73 views

### Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

As an example, here are all possible trees for the case $k=3$: On each node written is its arity (= the number of children). While this should be solvable by dynamic programming, I think there was a ...
105 views

### Generate random labeled tree with constrained edge lengths

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes ...
161 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 ...
6k 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 ...
9k 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?
3k 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 ...
881 views

### Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
5k views

### What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and ...
2k views

### Given a tree, find a vertex which maximizes the minimum distance to any leaf

If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf. I am sure this problem has been studied before. Does anybody know the ...
22k 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 ...
260 views

### Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing

I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is ...
132 views

744 views

### What algorithm should I use to find a minimal tree that include certain nodes within a graph?

Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or ...
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 ...
2k 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 ...
198 views

### Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...
112 views

### A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
400 views

### What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree ...
502 views

### What is the point of traversing a binary tree in preoder, inorder or postorder?

Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
1k 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 ...
669 views

### What is the expected number of nodes at depth d of a tree after i random insertions

Suppose one wanted to build a tree at random. Let the first insertion at step $i = 1$ be the root node. From here, nodes are inserted into the tree at random one at a time. How would one go about ...
2k views

### How to select a binary tree node uniformly at random

The exercise I'm trying to solve is You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method ...
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 ...