# Tagged Questions

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.

15 views

### How to draw prefix and postfix binary tree?

I have drawn these two binary trees. The ordered set of numbers is [-9, -5, 0, 1, 5, 7, 8, 10, 11] The first one is in prefix order and the second is in postfix order, but I'm not sure if my ...
20 views

### Which of the statements are true for travelling sales man problem of a greedy algorithm [on hold]

Which of the statements are true for travelling sales man problem of a greedy algorithm work’s for in complete graph also Krushkal’s algorithm gives a sub-optional solution in general Both $(1)$ and ...
16 views

### Combinations over tree nodes

Assuming to have a generic tree, how can I calculate all the possible combinations of 1,2,3...n nodes (with n that represents the number of nodes at a certain level of the tree) that can be generated ...
30 views

### Transforming generating functions into algorithms that generate combinatorial objects

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities). However, I'm not interested ...
544 views

### Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
5k views

### Finding number of homeomorphically irreducible trees of degree N

There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree 10. This is discussed in many places, such as here and is ...
23 views

### Binary tree traversal with fixed final node

What type of traversal is this called? Given a root node A and final node B: ...
15 views

### adjacency in a 4 tree

I have a mesh that is designed to partition a physical space with varying resolution. Basically the size of individual mesh cells varies depending on the location within the mesh (Visual Diagram) I ...
30 views

### Find number of possible root values for an n nodes avl tree

Be an avl tree with 20 nodes with values from 1 to 20. What are the possible values for the root node. ? I was thinking to find minimum and maximum height but I don't know what to do after that. Does ...
566 views

### Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
16 views

### Points with shortest distance always form an edge of a delaunay triangulation.

So I have to proof the following: Points with shortest distance to each other always form an edge of a delaunay triangulation/minimal spanning tree. Since minimal spanning tree is a subtree of a ...
29 views

### number of vertices with degree one in Tree given max. degree $\Delta$

Given a Tree $T$ with max. degree $\Delta > 1$ show that there are at least $\Delta$ vertices with degree exactly one. The solutions in the book I'm working with do not include (at least ...
42 views

### Full binary tree proof validity: Number of leaves $L$ and number of nodes $N$

I'm working through the full binary tree proofs for a blog post I'm writing and I want to make sure I'm not missing anything. This particular proof focuses on relating the number of total nodes $N$ to ...
24 views

### Finding number of leaves in a tree of 60 nodes in which 10 are of degree 3

I'm kinda stuck with this and can't seem to solve this question. Let G be a tree with 60 nodes, 10 of those nodes are of degree 3, there are no nodes with a degree larger than 3. How many leaves are ...
20 views

### Approximate perfect matching through MST

If I compute a minimum spanning tree T in a graph with an even number of vertices and T contains a perfect matching M (which is unique in this case), can I get some approximation guarantee on the ...
76 views

### Full binary tree theorem proof validity?

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is ...
24 views

### prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

I'm a discrete math student and I've bumped into the following question. I tried to prove it and specifically in first part I thought of two ways of proving it. but in each of the ways the proof looks ...
71 views

### Is there tree-based numeral system? [closed]

Preferrably such that ((()) ()), (() (())), (((()))), (() () ()) all were different numbers and any tree can be a number.
37 views

### How to describe a set of paths in a graph with as few nodes as possible? [migrated]

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
28 views

### Monte Carlo Search Tree iterations

I have had this example in my exam last week and I can not figure out how to solve it. I have watched lots of tutorials on Monte Carlo Search Tree but I can't still understand this algorithm properly. ...
12 views

### Easy References for understanding Grossmann and Larson rooted trees?

I am an undergraduate student doing a project on rooted trees. I was wondering if anyone would know any easy to understand references that explains Grossman and Larson's Hopf Algebra on rooted trees? ...
20 views

### Number of nodes satisfying a certain property on a binary tree

Fix a large integer $M$ and construct a binary tree as follows. Assign the root node by the integer $0$. If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and ...
72 views

### Complete Graph with odd degree

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with odd degree of its ...
2k views

### Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: Since the matchings are perfect, each vertex has degree $0$ or $2$ in the symmetric difference, so ...
484 views

### Min and max height of a binary tree

Suppose I have n nodes, how can I find the max and min height of a tree? I've seen varying statements for the min height such as log2 (n) and log2 (n+1) but I wasn't sure which was correct and I am ...
73 views

### Finding the maximum length of a minimum spanning tree

Graph G has 4 vertices/nodes and 5 edges. It is also connected. Its edges have the following weights: 5, 8, 10, 16, 18. The minimum length for a minimum spanning tree of graph G would be ...
59 views

### Enumerate out-trees that include a set of nodes in a directed graph

Given a digraph A, and an N set of nodes in the digraph. I need to enumerate the set of out-trees that contain those nodes. Where all the the out-trees leaves terminate on a node in set N. EDIT: I am ...
30 views

### Evaluating an arithmetic abstract syntax tree [closed]

This might be very simplistic for this forum (apologies, if so). How does one evaluate the tree below. I am not looking for a solution, just assistance in how to evaluate it: I assume I start at ...
37 views

### Find a DFS,BFS spanning tree.

Is my answer right? I think I understood the definition of BFS and DFS spanning tree, but I'm not sure my answer is right. If it is wrong, please correct it.
44 views

### Permutation of keys inserted into a tree?

Give the fraction of permutations of the keys $A$ through $G$ that will, when inserted into an initially empty tree, produce the same Binary search tree as does $A$ $E$ $F$ $G$ $B$ $D$ $C$ ANSWER: (...
2k views

### Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
42 views

### maximizing alpha-beta puning.

I was searching a more pertinent place to post artificial intelligence concerned question, but some results pointed me to similar questions posted here, thus I chose math.se, now let's get through ...
2k views

### Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
34 views

### Tree properties

I am reviewing Diestel's Graph Theory and we are asked to prove that the following are equivalent: (i) $T$ is a tree. (ii) Any two vertices of $T$ are linked by a unique path in $T$. (iii) $T$ is ...
199 views

### Pythagoras tree bounding size

The Pythagoras tree is a fractal generated by squares. For each square, two new smaller squares are constructed and connected by their corners to the original square. The angle of the triangle formed ...
54 views

61 views

### Counting the numnber of (labelled and unlabelled) rooted trees on $n$ vertices with height $h$

As far as I know, the number of labelled rooted trees on $n$ vertices is $n^{n-1}$. Is there a known result for counting the number of (labelled and unlabelled) rooted trees on $n$ vertices having ...
38 views

### Number of ordinal trees (aka rose trees) with n nodes, of depth d, with l leaves [closed]

Is computing the number of ordinal trees (also known as "Rose trees") with $n$ nodes, of depth $d$, with $l$ leaves an open problem? I assumed at first that it was a known results but I could not ...
125 views

### A few questions about a relationship between some integer sequences and infinite recursive trees

In his book Gödel, Escher, Bach Douglas Hofstadter defines the following two integer sequences: Hofstadter G-sequence: $a(n)=n-a(a(n-1))$ Hofstadter H-sequence: $a(n)=n-a(a(a(n-1)))$ He says ...
18 views

### Terminology for property of two branches of a tree

Consider a tree $T$. A branch $B$ of a tree $T$ is just a proper subtree of $T$ (that is a subtree $B \subset T$ and $B \neq T$). Lets consider $B_1$ and $B_2$, two branches of a tree such that $B_1$ ...
34 views

### Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be $8$. ...
930 views

### Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
34 views

### Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. [duplicate]

Let $G = (V, E)$ be a finite graph. (A) Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. (B) Assume that $|V | = |E| + 1$. Find an example that $G$ is not a tree.
14 views

### Algorithm for finding all maximum out-trees in a digraph

If we have a directed graph, and the graph contains subgraphs which are out-trees. We could find the set of out-trees, such that it does not contain any out-tree that is contained by another out-tree. ...
32 views

### KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct ...
86 views

### Existence of $\lambda^+$ Aronszajn trees when $\lambda$ is regular and $2^{<\lambda}=\lambda$

While I was dealing with Aronszajn trees I found the following exercise from Kunen's old book. If $\kappa=\lambda^+$ and $\lambda$ is a regular uncountable cardinal and $2^{<\lambda}=\lambda$ ...
### Which of the following is NOT true for $G$?
$G$ is a graph on $n$ vertices and $2n−2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ ...