Results 1 to 6 of 6

Math Help - Binary trees

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Binary trees

    This is a task from Kenneth Rosen's "Discrete Mathematics and its applications" book.

    How can I use structural induction to show that l(T) (the number of leaves of T) is 1 more than i(T) (the number of internal nodes of T), where T is a full binary tree?

    I am completely lost on this one,
    I have that the number of leaves is: 2^h, with h being the height of the tree, and obviously 2^h - 1 being the number of internal nodes.

    Total number of nodes n = 2^h + 2^h - 1

    But I don't see how I should set up the basis step nor the inductive step, or should I use a recursive step?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    This is a task from Kenneth Rosen's "Discrete Mathematics and its applications" book.
    Mmmm, Rosen...



    Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if P(T_1) and P(T_2) hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

    The first step is to come up with P. Here it is easy: P(T) is l(T) = i(T) + 1. Next, prove P for the single-node tree. For the induction step, suppose P(T_1) and P(T_2) hold, i.e.,

    l(T_1)=i(T_1)+1 and l(T_2)=i(T_2)+1. (*)

    Let's call the whole tree T. Express l(T) through l(T_1), l(T_2) and i(T) through i(T_1), i(T_2). Try to prove P(T) from (*).
    Last edited by emakarov; March 3rd 2011 at 12:55 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Are you saying that the graph above is a tree?
    But trees are a-cyclic.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    You are right, the graph is not a tree. It's a schematic picture. The triangles represent the subtrees.

    Edit: Drew the triangles in dashed lines to distinguish them from the graph edges.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by emakarov View Post
    Mmmm, Rosen...



    Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if P(T_1) and P(T_2) hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

    The first step is to come up with P. Here it is easy: P(T) is l(T) = i(T) + 1. Next, prove P for the single-node tree. For the induction step, suppose P(T_1) and P(T_2) hold, i.e.,

    l(T_1)=i(T_1)+1 and l(T_2)=i(T_2)+1. (*)

    Let's call the whole tree T. Express l(T) through l(T_1), l(T_2) and i(T) through i(T_1), i(T_2). Try to prove P(T) from (*).
    Basis step:

    P(single node): l(single node) = i(single node) + 1 \Longrightarrow 1 = 0 + 1

    Inductive step:

    P(T) : l(T) = i(T) + 1
    P(T) : l(T_1) + l(T_2) = i(T) + 1 (by recursive formula of l(T) )
    P(T) : l(T_1) + l(T_2) = i(T_1) + i(T_2) + 1 + 1 (by recursive formula of i(T) )

    Is this correct at all? What more do I need to complete the proof?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    I think you got the idea. I'll be a bit pedantic below.

    Quote Originally Posted by posix_memalign View Post
    Basis step:

    P(single node): l(single node) = i(single node) + 1 \Longrightarrow 1 = 0 + 1
    The left-hand side is what you need to prove. You can't conclude anything from it ( \Longrightarrow) because you have not proved it yet. I would write: l(\bullet)=1, i(\bullet)=0\Longrightarrow l(\bullet)=i(\bullet)+1.

    Inductive step:

    P(T) : l(T) = i(T) + 1
    P(T) : l(T_1) + l(T_2) = i(T) + 1 (by recursive formula of l(T) )
    P(T) : l(T_1) + l(T_2) = i(T_1) + i(T_2) + 1 + 1 (by recursive formula of i(T) )
    First, the relationship between these three lines is not clear. Is it what you need to prove? Is it the induction hypothesis? Does the first line imply the second or vice versa?

    Also, instead of "P(T) : l(T) = i(T) + 1", it is better to write "P(T) is l(T) = i(T) + 1" or "P(T) means l(T) = i(T) + 1" or "P(T) iff l(T) = i(T) + 1".

    Generally, for each statement you write, it should be clear where it follows from or whether you plan to prove it. So, I would write

    By induction hypothesis,

    l(T_1)=i(T_1)+1 and l(T_2)=i(T_2)+1. (1)

    Also, from the picture we know that

    l(T)=l(T_1)+l(T_2) (2)

    and

    i(T)=i(T_1)+i(T_2)+1. (3)

    Therefore,

    \begin{aligned}<br />
l(T)&=l(T_1) + l(T_2) &&\mbox{by (2)}\\<br />
&= i(T_1)+1+i(T_2)+1 &&\mbox{by (1)}\\<br />
&= i(T)+1 &&\mbox{by (3)}<br />
\end{aligned}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The number of possible binary trees with n nodes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2011, 05:33 AM
  2. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 6th 2009, 12:05 PM
  3. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 28th 2009, 02:38 AM
  4. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2008, 11:43 AM
  5. binary trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2006, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum