Experts are full of valuable knowledge and are ready to help with any question. Credentials confirmed by a Fortune 500 verification firm.

Get a Professional Answer

Via email, text message, or notification as you wait on our site. Ask follow up questions if you need to.

100% Satisfaction Guarantee

Rate the answer you receive.

Ask David Your Own Question

David,
Tutor

Category: Homework

Satisfied Customers: 2310

Experience: PhD in Theoretical Physics

394177

Type Your Homework Question Here...

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.)

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

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.

JustAnswer.com...has seen a spike since October in legal questions from readers about layoffs, unemployment and severance.

Web sites like justanswer.com/legal ...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

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!!!!AlexLos 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.GPHesperia, CA

I couldn't be more satisfied! This is the site I will always come to when I need a second opinion.JustinKernersville, 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. EstherWoodstock, 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. RobinElkton, 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.DianeDallas, TX