Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A binary tree question(java)

  1. Feb 17, 2008 #1
    there is a given binary tree
    each of member are of a Node type
    Code (Text):

    class Node {
    int info;
    Node left;
    Node right;
    }
     
    in the info part of each node we have a number.
    in each one of his leaves we have some number
    and in each one of its roots (crossroads) we have zeros.

    my gole is to build a method which calculates the difference between the
    sums of the leaves in the right subtree of T
    and the sum of the leaves in the left subtree of T
     
  2. jcsd
  3. Feb 19, 2008 #2

    malawi_glenn

    User Avatar
    Science Advisor
    Homework Helper

    just visit all nodes in left sub-tree, if both Node.left && Node.right == null, increase the number of leaves.
    Then visit right-subtree and do the same.
     
  4. Feb 20, 2008 #3
    what do you meen increase the number of leaves
    i need to count them i cant add another object
     
  5. Feb 20, 2008 #4

    Eus

    User Avatar

    Hi Ho!

    A recursive algorithm will nicely solve this.
    The idea is that we know that the base case will be when a node is a leaf. In this case the height difference will be just 0.
    If it is not a base case, simply solve the problem recursively by traversing the left child and the right child.

    Here is the code if you do not want to think about how to implement such a solution.

    Code (Text):

    int calculate_height_difference (Node node)
    {
        if (node.left == null && node.right == null)
        {
            return 0;
        }

        return calculate_height_difference (node.right) - calculate_height_difference (node.left);
    }
     
    Best regards,
    Eus
     
    Last edited: Feb 20, 2008
  6. Feb 20, 2008 #5

    malawi_glenn

    User Avatar
    Science Advisor
    Homework Helper

    I meant increase the number of leaves VISTIED.
     
  7. Feb 23, 2008 #6
    comment

    >> what do you meen increase the number of leaves

    It means you have reached a leave, so count it by increasing the leaf_count
     
  8. Feb 23, 2008 #7

    malawi_glenn

    User Avatar
    Science Advisor
    Homework Helper

    yes but a recrusive method is better.

    If your classes are:

    class TreeNode{

    Object data;
    TreeNode left;
    TreeNode right;

    constructor...

    }


    class Tree{

    TreeNode head;

    .. other methods..

    ----------------

    So you first have a general method like:

    diffLeftRight(){

    return Math.abs(numberOfLeaves(head.left) - numberOfLeaves(head.right);

    }


    numberOfLeaves(TreeNode tr){

    if(tr == null)
    return 0;
    else if(tr.left == null && tr.right == null)
    return 1;
    else if(tr.left == null && tr.right != null)
    return numberOfLeaves(tr.left);
    else if(tr.left != null && tr.right == null)
    return numberOfLeaves(tr.right);
    else
    return numberOfLeaves(tr.left) + numberOfLeaves(tr.right);

    }

    Maybe you need to modify it a bit, but this is the general idea of recursion
    }
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A binary tree question(java)
  1. Binary tree algoritms (Replies: 5)

  2. Binary Search Tree C++ (Replies: 1)

  3. Binary tree (Replies: 5)

Loading...