Results 1 to 2 of 2

Math Help - Binary Trees

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    Binary Trees

    Can someone please check my answers.
    Let t be a binary tree with 2148 vertices.

    1)Is it possible that the height of T is less than 8? No, because -1 + 2 ^(7+1) = 255.

    If t is a full then:

    2) the number of leaves? 2047
    3) the number of internal vertices? 1124
    4) the height of t? 11.


    Can someone check these please. Someone on the forum gave me a formula but im not sure if i used it correctly. Thanks!
    Last edited by kurac; June 1st 2009 at 05:30 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2009
    Posts
    6
    Quote Originally Posted by kurac View Post
    Can someone please check my answers.
    Let t be a binary tree with 2148 vertices.
    Are you sure the number of vertices (nodes) is 2148 and it is a full binary tree? isn't a full binary tree a tree where each vertex has two children except the leaf nodes?

    if so I don't think a full binary tree can have an even number of vertices (nodes), because the number of nodes in each level except the root is even and that means the full tree should have an odd number of vertices (even + odd = odd). The number of vertices a specific level is given by the equation:

    number of vertices in level L = 2^L

    so in level 0 (root) we have 2^0 = 1 vertix
    in level 1 ...... we have 2^1 = 2 vertices
    in level 2 ...... we have 2^2 = 4 vertices


    anyway ...

    Quote Originally Posted by kurac View Post
    1)Is it possible that the height of T is less than 8? No, because -1 + 2 ^(7+1) = 255.
    Your answer is true. because the height of this tree should equal to the Integer[log2(2148)] = Integer[11.0687783] = 11


    Quote Originally Posted by kurac View Post
    If t is a full then:

    2) the number of leaves? 2047
    3) the number of internal vertices? 1124
    4) the height of t? 11.


    Can someone check these please. Someone on the forum gave me a formula but im not sure if i used it correctly. Thanks!
    I think there is something wrong here, because the number of nodes should be equal to the summation of the internal vertices and the leaves.

    number of nodes = number of leaves + number of internal vertices
    2148 = 2047 + 1124
    2148 = 3171 which means there is something wrong. Thats why I doubt that there is a full binary tree which contains 2148 vertices.

    Anyway, as far as I know,
    the number of internal nodes = number of all nodes in the tree / 2 + 1
    the number of leaves = number of nodes in the tree / 2


    lets consider a full binary tree of 7 vertices (nodes), so n = 7:
    ........*
    .....*.....*
    ...*.*...*.*

    number of internal vertices = n/2 = 7/2 = 3
    number of leaves vertices = n/2 +1 = 7/2+1 = 4
    height of tree = Integer[log2(n)] = Integer[log2(7)] = Integer[2.8] = 2



    I hope that helped
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary trees
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 4th 2011, 08:43 AM
  2. The number of possible binary trees with n nodes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2011, 06:33 AM
  3. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 28th 2009, 03: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, 12:43 PM
  5. binary trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2006, 08:31 PM

Search Tags


/mathhelpforum @mathhelpforum