# Find the size and depth of a tree

Posted on

Problem

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.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);
}
}
``````

Solution

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

// Add node to to tree
// results.size++
//   results.height++

RemoveNode(TreeNode node, TreeNode tree)
// Remove node from tree
// results.size--
//   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.

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.