Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [trees]

For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

Trees are an important topic in graph theory. A tree is a connected graph with no cycles. They are of enormous practical importance in applied mathematics.

For example, in a connected weighted graph, it is interesting to know how to find a subgraph which is a tree and which maximizes or minimizes the total weight of the subgraph. A subgraph of a graph $G$ which is a tree that touches all nodes of $G$ is called a spanning tree for $G$.

For instance, imagine a network of electrical systems, such as a telephone system, between nodes. Suppose that signals can travel through any path in the network, passing through intervening nodes to get to the final destination. The amount of wiring can be reduced by deleting portions of cycles in the graph of the network. The graph can eventually be reduced to a tree, and all nodes remain connected and accessible through the network.

Dijkstra's algorithm is an effective way to determine the lowest-weight spanning tree for a given connected graph.

2015 questions
0
votes
1 answer

binary search tree rotations

if I have two binary search trees with the same keys(n keys) but not identical, I can get from the first tree to the other by maximum n tree rotations. how can I prove it? for example I can get from tree 1 to tree 2 by one rotation:
KIMKES1232
  • 425
  • 3
  • 9
0
votes
0 answers

Reconstructing (rooted) trees from partial (rooted) subtrees

Given a tree $T$ and a vertex $v$ in $T$, let $N_r(T)$ be the set of all vertices at distance at most $r$ to $v$. Furthermore, let $T_r(v) = T[N_r(v)]$, the subtree of $T$ induced by $N_r(v)$. Fix $v$ and let its neighbors be $w_1,\ldots, w_t$.…
Slugger
  • 5,556
0
votes
1 answer

Find the branching factor in a tree given the total number of nodes in the tree

Suppose I know the number of total employees and the number of levels in the company hierarchy. Assuming that the number of subordinates a supervisor has is constant across the levels, how can I find the average number of subordinates per manager…
nakiya
  • 175
0
votes
1 answer

Finding the height of a perfect quadtree

I am sure this must be trivial but I can't find this specifically anywhere. I have a perfectly balanced, full quadtree. I know the total number of nodes in the tree. I want to find out the height without traversing the tree - what is the formula for…
KaiserJohaan
  • 103
  • 2
0
votes
1 answer

Maximum height of a quad tree

If we have a quad tree where each node must have 0 or 4 children, is there an expression that can me the maximum height of a quad tree with $n$ nodes?
Snowman
  • 2,664
0
votes
0 answers

Group pairs of numbers into sets

Apologies if the title does not articulate this very well but here is what I'm trying to accomplish: I have an array of pairs that represent links between the numbers in each pair. I need to derive from this array all the unique groups that the…
zeke
  • 101
0
votes
1 answer

What is this "tree function" I see every once in a while?

Sometimes I see or hear a reference to some kind of tree function in math, but every time I look it up, the term is so broad or vague that there's no consistent explanation of what it is or how it's used. Is there any kind of actual consensus on it?…
John Joe
  • 189
0
votes
0 answers

How to balance an avl tree with steps?

I am not getting how to balance an AVL tree, I have looked for the answers online but that was not clearing my doubts.
Zakria
  • 1
0
votes
0 answers

Expected number of leaves at a certain level of a "grown" binary tree

Let's say that we have a binary, not necessarily complete, tree. This tree is the result of a "duplication process" of an initial node (root). So initially we start with a single node (the root) that has these duplication probabilities: P[0] =…
jackscorrow
  • 101
0
votes
2 answers

Prove every tree with at least 1 edge has 2 leaves

Prove that every tree with at least $1$ edge has at least $2$ leaves (recall that a leaf is a vertex of degree $1$). Can anyone show me how to prove this question? Here's what I tried. Since it doesn't mention full trees, an ordered tree doesn't…
f.fans
  • 11
0
votes
1 answer

Trees with explicit formula

A ternary tree is an ordered tree where each node has either $0$ or $3$ children. Such a tree is full if all leaves are at the same distance from the root. Derive an explicit formula for the number of leaves and the total number of nodes, in a full…
f.fans
  • 11
0
votes
1 answer

Do red black trees have different rules and shapes?

I followed the rules of the insert operation listed at GeeksforGeeks. I used them to solve example 2 here. My solution below is different than the one in the same document. 32 (black) / \ 21 (black)…
Ahmad Abdelzaher
  • 19
0
votes
1 answer

Vertex and graphs . prove trees.

Can anyone tell me how to prove that every tree with at least 1 edge has at least 2 leaves? Im currently studyinng proof of trees.
studymaths
  • 287
0
votes
1 answer

How to construct a balanced search tree?

I'm not sure how to construct a balanced search tree out of a few numbers and their associated search probabilities. Please explain using the following example: 15 0.2 10 0.22 107 0.02 30 0.05 12 0.18 105 0.25 120 0.08
Ahmad Abdelzaher
  • 19
0
votes
1 answer

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 with a compelling argument that a tree of the above…
usernolan
  • 69
1 2 3 4
5
6