Binary Tree static methods in Java

Question

I have these instance methods in my Java implementation of Binary Tree and Search Binary Tree: getSize(), getHeight(), getDepth(), getPreOrder(), getInOrder(), getPostOrder() and getLevelOrder(). These methods use the root of the tree in others recursive methods that have a parameter Node. Which is more appropiate to use from the point of view of the OOP:

1. Using these recursive methods as static methods, because they use an object (Node) that doesn't belong to the actual class, and they don't use any class attributes,
2. They can be instance methods because they can use in a subtree of this tree and they don't use any static attributes,
3. or they may be in other static class like UtilsTree()?

Answer 1

From an OOP perspective I believe approach number 2 is the way to go. (Statics are in general often frowned upon in OOP.)

As I understand it, the method uses this as root, and then traverses the rest of the tree without calling any instance methods? This isn't too bad considering that the other nodes are of the same class, which means that the code is already shared among all objects. (The method can access private members of other instances and so forth.)

That being said, I think getSize, getHeight, getDepth, getPreOrder, getInOrder, getPostOrder and getLevelOrder can all be implemented as proper recursive instance methods. (Correct me if I'm wrong.)

A fourth option which isn't too bad would be to use a visitor pattern and have a NodeVisitor interface.

Answer 2

Some of those methods definitely should be non-static members since they relate directly to a specific instance.

tree.getSize() or tree.getDepth() is much easier to read and understancd than BinaryTree.getDepth(tree).

However one could argue that the methods getPreOrder(), getInOrder(), getPostOrder() can be static or even in their own class. You can think of that as a StrategyPattern for how to walk the tree.

TraversalStrategy.PREORDER.walk(tree);

might be a good idea instead of adding more methods. That way, if you ever need to add different ways to walk to the tree you don't have to keep adding methods to BinaryTree (Following the Open-Closed Principle)