• 100% Satisfaction Guarantee

David, Tutor
Category: Homework
Satisfied Customers: 2310
Experience:  PhD in Theoretical Physics
394177
David is online now

A binary tree can be recursively defined as follows. A single

Resolved Question:

A binary tree can be recursively defined as follows.
A single vertex is a binary tree. (This single vertex is the root of this binary tree.)
If T1 and T2 are binary trees, then so is the result of the following construction.
– Create a new vertex. (This vertex will become the root of the new binary tree.)
– Add an edge between this new root vertex and the roots of T1 and T2.
Prove the following for all binary trees:
• Root vertices either have degree 0 or 2 and are the only vertices with these degrees.
The number of degree 1 vertices is 2 more than the number of degree 3 vertices.
(Hint: It will be simpler to combine the two properties in a single proof.)
Submitted: 4 years ago.
Category: Homework
Expert:  David replied 4 years ago.

David :

here is the proof:

David :

First we prove that Root vertices either have degree 0 or 2.
Only two possibilities that we have.
1) if the vertex is the tree itself (just a point) then the degree is 0
2) if the vertex is constructed by joining to other two trees (hence the name binary)
in this case the degree is 2.
all other vertices do not have 0 or 2 degree, because it the vertex is NOT root, then
it there is a line coming to it and two lines going out (so the degree is 3)

David :

or

David :

or there is only one line coming to it (it will be the end of the tree and the degree is 1)

Customer:

There is another poof : The number of degree 1 vertices is 2 more than the number of degree 3 vertices.

Customer:

In this question need to proof two statement: a)The number of degree 1 vertices is 2 more than the number of degree 3 vertices b) The number of degree 1 vertices is 2 more than the number of degree 3 vertices

David :

ok give me a sec

Customer:

thx

David :

Here is the proof:
a) Above I've argued that vertices other than root can be of degree 1 or 3. and any vertex of degree 1 has a pair
that is joined to a vertex of degree 3 (by construction) and for the base case of a two step binomial
tree we have 4 vertices of degree 3 ans 2 vertices of degree 2.
Now, for any number of steps binomial tree we can break it into components of two
step binomial tree (by construction) by joining the root vertices to a new vertices.
but in this case the number of degree 3 in each 2 step binomial tree wil increase by 1, because the
root vertices becomes degree 3 vertex. so we can go by induction here:
If for tree T1 and tree T2 the numbers of degree vertices are n3 and m3 and the
degree 1 vertices were n3+2 and m3+2 correspondingly,then upon joining T1 and T2
the degree 1 vertices will be n3+2+m3+2 = n3+m3+4. But the number of degree 3 vertices
will be n2+m3+2 (note I add 2 because the root vertices of T1 and T2 now become degree 3 vertices)
as you see n3+m3+4 is 2 more than n3+m3+2, as expected.
DONE

Customer:

Hi are you still there

David, Tutor
Category: Homework
Satisfied Customers: 2310
Experience: PhD in Theoretical Physics
Customer: replied 4 years ago.
close it
Expert:  David replied 4 years ago.
Ok.

Ask-a-doc Web sites: If you've got a quick question, you can try to get an answer from sites that say they have various specialists on hand to give quick answers... Justanswer.com.
...leave nothing to chance.
Traffic on JustAnswer rose 14 percent...and had nearly 400,000 page views in 30 days...inquiries related to stress, high blood pressure, drinking and heart pain jumped 33 percent.
Tory Johnson, GMA Workplace Contributor, discusses work-from-home jobs, such as JustAnswer in which verified Experts answer people’s questions.
I will tell you that...the things you have to go through to be an Expert are quite rigorous.

What Customers are Saying:

• Wonderful service, prompt, efficient, and accurate. Couldn't have asked for more. I cannot thank you enough for your help. Mary C. Freshfield, Liverpool, UK
< Previous | Next >
• Wonderful service, prompt, efficient, and accurate. Couldn't have asked for more. I cannot thank you enough for your help. Mary C. Freshfield, Liverpool, UK
• This expert is wonderful. They truly know what they are talking about, and they actually care about you. They really helped put my nerves at ease. Thank you so much!!!! Alex Los Angeles, CA
• Thank you for all your help. It is nice to know that this service is here for people like myself, who need answers fast and are not sure who to consult. GP Hesperia, CA
• I couldn't be more satisfied! This is the site I will always come to when I need a second opinion. Justin Kernersville, NC
• Just let me say that this encounter has been entirely professional and most helpful. I liked that I could ask additional questions and get answered in a very short turn around. Esther Woodstock, NY
• Thank you so much for taking your time and knowledge to support my concerns. Not only did you answer my questions, you even took it a step further with replying with more pertinent information I needed to know. Robin Elkton, Maryland
• He answered my question promptly and gave me accurate, detailed information. If all of your experts are half as good, you have a great thing going here. Diane Dallas, TX

• LogicPro

Satisfied Customers:

4925
Expert in Java C++ C C# VB Javascript Design SQL HTML
< Last | Next >

LogicPro

Satisfied Customers:

4925
Expert in Java C++ C C# VB Javascript Design SQL HTML

Manal Elkhoshkhany

Satisfied Customers:

4538
More than 5000 online tutoring sessions.

Linda_us

Satisfied Customers:

3138
Post Graduate Diploma in Management (MBA)

Chris M.

Satisfied Customers:

2602
Master's Degree, strong math and writing skills, experience in one-on-one tutoring (college English)

F. Naz

Satisfied Customers:

2126
Experience with chartered accountancy

Bizhelp

Satisfied Customers:

1887
Bachelors Degree and CPA with Accounting work experience