Find the size and depth of a tree

Question

I have tried to implement two methods, one for finding the size of the tree and the other for finding the height of the tree. Can they be optimized further?

  package trees;
  import java.util.LinkedList;
  import java.util.TreeSet;
public class TreeNodeImpl {



    public TreeNodeImpl left ; 
    public TreeNodeImpl right; 
    public int Value ;
    public int height=1;

    public TreeNodeImpl newTreeNode(int value){
        TreeNodeImpl newNode = new TreeNodeImpl();
        newNode.Value = value;
        newNode.left = null;
        newNode.right = null ; 
        return  newNode;
    }

    public int   recSize(TreeNodeImpl node ){
            if(node == null){
                return 0 ;
            }
            else{
                return( recSize(node.left)+ 1 + recSize(node.right));
            }
    }
    public int recHeight(TreeNodeImpl node){

        if(node==null)
        {
            return 0;
        }
        else {


            if(node.left!=null||node.right!=null){
                height++;
                recHeight(node.left);
                recHeight(node.right);
            }
        return height;
        }
    }

    public static void main(String[] args) {
        TreeNodeImpl node = new TreeNodeImpl();
        node.Value = 6;
        node.left= node.newTreeNode(20);
        node.left.left = node.newTreeNode(30);
        node.right= node.newTreeNode(30);
        node.left.left.right = node.newTreeNode(34);
        node.left.left.left = node.newTreeNode(34);
        int Size = node.recSize(node);
        System.out.println(Size);
        int height = node.recHeight(node);
        System.out.println(height);
    }
}

Answer 1

For efficiency, there's no reason to be redundant. One walk of the tree can compute both height and size. A class can be used to hold the results of the walk:

// pseudo-code

class Results
  Integer height = 0
  Integer size   = 0

class TreeNode
  Results results()
  Integer height() = results.height
  Integer size()   = results.size

  TreeNode TreeNode(TreeNode[] nodes)
    // Build tree with left and right
    // Walk(tree)
    // return tree

  Walk(TreeNode tree)
    // update results.height
    // update results.size

  AddNode(TreeNode node, TreeNode tree)
    // Add node to to tree
    // results.size++
    // If (added node made tree taller)
    //   results.height++

  RemoveNode(TreeNode node, TreeNode tree)
    // Remove node from tree
    // results.size--
    // If (added node made tree shorter)
    //   results.height--

It is important to consider AddNode and RemoveNode and the basic tree constructor because knowing their logic makes it possible to avoid walking the tree at every change to determine depth...or to know that the tree structure may be arbitrarily unbalanced and that it must be walked after each change.

In any event, there is no reason to walk the more than once to determine its size, and there is some logic to having tree.size as a field of TreeNode.

This is essentially memoization and for any interestingly sized tree offers a huge performance improvement on repeated access for any data type as simple as an integer.

Answer 2

The formatting is all over the place, which is distracting and makes the code hard to read.

The suffix Impl in TreeNodeImpl is unnecessary, as are the rec prefixes for recSize and recHeight.

It's not clear why newTreeNode should exist; this looks like work that should be done in a constructor.

Neither of the imports java.util.LinkedList and java.util.TreeSet are used and should be removed.

Having recSize and recHeight take a node as a parameter leads to strange-looking code like node.recSize(node).

The biggest problem though is that successive calls to recHeight will return different values.