Results 1 to 4 of 4

Math Help - Graphs (algorithm)

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    5

    Graphs (algorithm)

    Hi,
    Let n be a node in a binary, and let l(n) give its left child and r(n) give its right child. I am supposed to write a recursive algorithm MaxBranch(l,r,x), which returns the length of the longest branch of the tree (x is the root of the tree, and length of a branch is the number of arcs on the path from the root to a leaf). I'm not really sure how the psuedocode would look like. If someone could at least give me a hint, I would really appreciate it.

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by alireza1989 View Post
    Hi,
    Let n be a node in a binary, and let l(n) give its left child and r(n) give its right child. I am supposed to write a recursive algorithm MaxBranch(l,r,x), which returns the length of the longest branch of the tree (x is the root of the tree, and length of a branch is the number of arcs on the path from the root to a leaf). I'm not really sure how the psuedocode would look like. If someone could at least give me a hint, I would really appreciate it.

    Thanks in advance
    MaxBranch(l,r,x) = max (MaxBranch(l(l), r(l), l), MaxBranch(l(r), r(r), r) + 1.

    That's about as good as I can do, aside from defining MaxBranch to be 0 when neither l(n) nor r(n) exist.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by icemanfan View Post
    MaxBranch(l,r,x) = max (MaxBranch(l(l), r(l), l), MaxBranch(l(r), r(r), r) + 1.

    That's about as good as I can do, aside from defining MaxBranch to be 0 when neither l(n) nor r(n) exist.
    I just thought of something else: You want to define MaxBranch(l, r, x) to be MaxBranch (l(l), r(l), l) + 1 when r(x) does not exist but l(x) exists and MaxBranch(l, r, x) to be MaxBranch (l(r), r(r), r) + 1 when l(x) does not exist but r(x) exists. So you have to make 3 initial tests before you can iterate.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2008
    From
    Auckland, New Zealand
    Posts
    4

    Arrow

    The algorithm should be something like this:

    Code:
    public int MaxBranch(node node){
       int length = 0;
       int lengthMax = 0;
       TestChild (node, length, lengthMax);
       return lengthMax
    }
    
    public int TestChild (node node, int length, int lengthMax){
       if (node.l(n) != null){
          length = length ++;
          TestChild (node.l(n), length, lengthMax);
       }
       if (length > lengthMax){
          lengthMax = length;
       }
       if (node.r(n) != null){
           length = length ++;
           TestChild (node.r(n), length, lengthMax);
       }
       if (length > lengthMax){
           lengthMax = length;
       }
       return lengthMax;
    }
    Not 100%, but I hope that helps you visualise at least. Basically, you test if there is a left-node, if there is you add one to the length and then test if that node has a left node.....once you get a no, you compare that length to the greatest length so far; then check for right node etc.

    It's recursively calling itself within the algorithm.

    Hope that helps.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set in an algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 18th 2011, 11:36 AM
  2. [SOLVED] Graphs, Dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2011, 04:20 PM
  3. Yen's algorithm - shortest path - Graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 12th 2009, 12:52 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 23rd 2009, 11:43 AM
  5. Algorithm
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 26th 2007, 06:42 AM

Search Tags


/mathhelpforum @mathhelpforum