-2
\$\begingroup\$

I have to write methods for a binary tree that has positive integers as values. These are not full methods. They are supposed to be written in pseudocode.

a) Count number of nodes in a Tree

countNodes(TreeNode root){
    if(root == null)
        return 0;
    else{
        TreeNode left = root.getLeftChild();
        TreeNode right = root.getRightChild();
        return (countNodes(left)+countNodes(right)) + 1;
    }
}

b) Compute the height of a tree

height(TreeNode root){
    if(root == null)
        return 0;
    else{
        return Math.max(height(root.getLeftChild()), height(root.getRightChild()) +1;
    }
}

c) Find the maximum element

maxElem(TreeNode root){
    if(root == null)
        return 0;
    else{
        int temp = 0;
        temp = Math.max(maxElem(root.getLeftChild()), maxElem(root.getRightChild()));
        return Math.max(root.getValue, temp);
    }
}

d) Find the sum of the elements

sum(TreeNode root){
    if(root == null)
        return 0;
    else{
        return (sum(root.getLeftChild()) + sum(root.getRightChild())) + root.getValue();
    }
}

e) Find the average of the Elements

average(TreeNode root){
    double sum = sum(root);
    double elems = countNodes(root);
    return sum/elems;
}

f) Find a Specific Item

search(int i, TreeNode root){
    if(root == null)
        return false;
    else if(root.getValue == i)
        return true;
    else{ 
        return search(i, root.getLeftChild);
        return search(i, root.getRightChild);
    }
}

g) Determine whether an item is an ancestor of another

isAncestor(TreeNode p, NodeNode c){
    if(p==null)
        return false;
    else
        return (c in p.getLeftChild() || c in p.getRightChild())
}

h) Determine the highest level that is full

maxFull(TreeNode root)
    if(root == null)
        return 0;
    else{
        return(numNodes in level h == 2^h - 1)
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm afraid that psuedocode is off-topic as per the FAQ. \$\endgroup\$ Apr 2, 2013 at 1:50

1 Answer 1

1
\$\begingroup\$

Even if you have to use pseudocode, you should do some checks. Either in pseudcode (calculcate by hand) or implement it in any language.

Most of them look ok, some comments:

    return search(i, root.getLeftChild);
    return search(i, root.getRightChild);

This can not work, the second return is unreachable. You could do something like

if (current == null)
    return -1; 
...
if (left != -1) return left;
return right;

I do not understand your isAncestorfunction (it is not clear to me what should be done and which argument is responsible for which part). From the description, it looks a bit ridiculous, because you just have to return a.left == b || a.right == b (the difference to your code is the in. Typically in means is contained in the set, but a node is normally not a set.


For maxFull, I think you need to give more details instead of just writing the text and the function is probably wrong (if you have a balanced binary tree, root is level zero. Then we have at level 1 two nodes if full. Your formula would expect one node). You have to do something like return 1 + Math.min(maxfull(left), maxfull(right)), but this depends on your definition for full.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.