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.

learn more… | top users | synonyms

0
votes
1answer
48 views

Some questions about first-order logic (arising from a book by Raymond M Smullyan)

Recently, I got confused when reading a book about first order logic written by Raymond M smullyan. Chapter 1 page 9:When introducing the notion "Formation tree", smullyan define a formation tree for ...
0
votes
0answers
20 views

Can a search-tree be reversed in order to find more solutions?

consider a search-tree that we already know that if we start from the start-node (S), and go to nodes A1, B2, C1, then we get to the Goal-node. We have this solution, but we don't know the other nodes ...
0
votes
1answer
92 views

proof: center of a tree lies on the longest path

how can I make a proof of this property? I mean, given a weighted tree(with positive costs), how can I proof that the center of such a tree lies on the longest path?? I read to the first answer of ...
0
votes
1answer
58 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
0
votes
1answer
41 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
0
votes
0answers
32 views

Search L leaves smaller than node N

So in my binary $kd$-tree I have a node $N$. Now I search for the number of leafs $L$ "on the left" side of $N$ (this includes the left child branch of $N$ and all parents where the node is a right ...
0
votes
0answers
44 views

How to calculate branching factor of uniform tree

For a uniform tree of depth $d$ and if a particular problem has $N$ nodes then the $b*$ branching factor is $N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$. For a depth of 5 and N = 52 how is it that the ...
0
votes
2answers
48 views

Finding an equation for a growth formula

Given a tree that has three nodes each level I want to find the formula that predicts the number of all nodes with a given tree height. I fitted the data into Numbers with an exponential function ...
0
votes
0answers
100 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
0
votes
0answers
192 views

D ary tree node math

A d-ary tree is a rooted tree in which each node has at most d children (c) Suppose the tree has n nodes. What is the minimum the depth could possibly be, in terms of n and d? You can leave your ...
0
votes
1answer
60 views

Counting the number of trees on $[n]$

Let $T_{n}$ be the number of trees on $[n]$. Explain the identity below in terms of $T_{n}$ and prove it. $2(n-1)n^{n-2}=\sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}(n-k)^{n-k-1}.$ So far I've got that ...
0
votes
0answers
16 views

Measuring values at nodes of two independent but now connected trees

I am not sure if this the right forum for this question and I hope I am providing enough details on what I want to accomplish. I have an application that has multiple trees - Tree 1 - is categories/ ...
0
votes
1answer
80 views

Unique solution for a given pre- and post-order of a rooted tree

Decide the picture of a rooted tree with pre-order $a,b,c,d,e,f,g,h$ and post-order $d,e,f,g,h,c,b,a$. Show that there always is a unique solution for a given pre- and post-order of a rooted tree. My ...
0
votes
1answer
55 views

Minimal Red-Black tree with depth 3

I'd like to ask what is minimal RBT with black depth 3. Is this following RBT ? Values are not important. And that tree can't have depth 2 or 1.
0
votes
0answers
21 views

Simplification of a dervived binary tree with n nodes [duplicate]

hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
0
votes
0answers
293 views

What is the algorithm to sort 5 elements in 7 binary comparisons?

I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
0
votes
1answer
42 views

Identify Type of Recursive Sequence?

I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
0
votes
0answers
106 views

Nilpotency of the adjacency matrix of a directed tree network

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
0
votes
0answers
92 views

Straight skeleton is a tree

Can anybody give me a hint on how to prove that the straight skeleton of every polygon is a tree. Here is the definition of the straight skeleton (taken from Wikipedia): The straight skeleton of a ...
0
votes
1answer
345 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
0
votes
1answer
183 views

has deleting node in a binary search tree Displacement feature?

I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to ...
0
votes
1answer
603 views

M-ary tree problem

A full $m$-ary tree $T$ has 81 leaves and height 4 1) Give the upper and lower bounds for $m$ 2) What is $m$ if T is also balanced? [with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...
0
votes
1answer
343 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
0
votes
0answers
287 views

Depth-first spanning tree?

I am going to identify tree edges and back edges in an undirected graph. The graph consists of $5$ nodes, the edges between these nodes are as shown below: Suppose starting with $v_1$, after a ...
0
votes
0answers
49 views

An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...
0
votes
1answer
319 views

Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?
0
votes
0answers
129 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem, unfortunately I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
-1
votes
1answer
47 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
-1
votes
0answers
18 views

Tree stored as adjacency matrix

Can tree be stored as an adjacency matrix? My answer: No. Reason: all though it can be stored as adjacency matrix, but the hierarchy is not maintained when stored as a matrix. Also, who are the ...
-2
votes
1answer
212 views

Parse tree parenthesis notation [closed]

Can anyone help me understand this in a tree format? What the indentation means? How do I represent this in a tree? ...