Results 1 to 3 of 3

Math Help - Binary Tree Question

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    1

    Binary Tree Question

    Hello Math Help Forum! This is my first post. See, I have a final tomorrow and have greatly procrastinated on studying. The professor gave a practice final and I missed all of the solutions, and I do not understand how to solve the following question:

    Let T be the full binary tree with height n with 2^n terminal vertices. Let r denote the root. Define a weight on the edges of T as follows: If an edge e connects a vertex with its left child, define w(e)=0. If an edge connects a vertex with its right child, define w(e)=1. Now let P be the set of simple paths from r to the terminal vertices. Note that |P| = 2^n since there is one simple path from r to each terminal vertex. Let P(k) be the set of paths in P with total weight k. Show |P(3)|<= n^3.

    (Recall that the weight of a path is the sum of weights of the edges in the path).

    My first instinct was induction but that didn't work. My next was a recurrence relation but I got lost. Any tips?? Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Binary Tree Question

    Isn't it true that |P(3)|=\binom{n}{3}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Binary Tree Question

    Just an aside: this depends on a couple of definitions, as height is sometimes defined as 0 for a tree of size (node count) 1, but other times is defined as 1 for a tree of size 1 (if the order zero graph is allowed, which is extremely useful for setting up the recursive structure of the binary tree in computer science). Based on your formula it seems you're using the former definition.

    This problem is essentially asking "in a full tree of n+1 levels, prove there are at most n^3 paths from root to leaf that branch right exactly three times". You will get n branch choices, one choice for each level indexed from 1 to n. You have to choose exactly three of these to head to the right. So emakarov is correct.

    (This seems like a very silly question. I'm not sure what content area they are trying to assess here outside of basic logic.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binary tree math proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 14th 2012, 03:24 AM
  2. asimptotic value of height of binary tree
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 20th 2011, 12:08 PM
  3. [SOLVED] Full Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2010, 05:22 PM
  4. Induction for binary tree.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 30th 2010, 11:17 AM
  5. [SOLVED] Binary tree - number of leafs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 3rd 2008, 08:11 AM

Search Tags


/mathhelpforum @mathhelpforum