Package io.openml.gearbox.binarytree.pathvisitor

Class AbstractRootToLeafPathVisitor<T,R>

java.lang.Object
io.openml.gearbox.binarytree.pathvisitor.AbstractRootToLeafPathVisitor<T,R>
Type Parameters:
T - The type of the value/data stored in each node of the binary tree being path-traversed
R - The type of value/object that is to be returned as the result of the path-traversal
Direct Known Subclasses:
DepthCalculator, RootToLeafPathsMaker
public abstract class AbstractRootToLeafPathVisitor<T,R> extends Object
A base class that implements the path-traversal algorithm of a binary tree.

A path-traversal is defined as traversing the tree by following root-to-leaf path order from left to right while maintaining each single path. For example, a path-traversal of the following tree 

      1
    /  \
   2   3
  / \   \
 4  5   6
is 1 -> 2 -> 4 -> 5 -> 3 -> 6. The fundamental difference between path-traversal and pre-order traversal is that path-traversal works for algorithm in which root-to-leaf path needs to be calculated while pre-order traversal does not. For example, all root-to-leaf paths of a binary tree or depth of a binary tree can be found using path-traversal algorithm. These are, however, not doable using pre-order traversal algorithm

This algorithm is not designed for implementing algorithm that could possibly terminate in the middle of the traversal(such as search), because this algorithm does not terminate when the terminating condition is satisfied (such as the search target is found); instead it will keep traversing until all nodes in the tree have been visited.

  • Constructor Details

    • AbstractRootToLeafPathVisitor

      public AbstractRootToLeafPathVisitor()

  • Method Details

    • getVisitResult

      public abstract R getVisitResult()
      Retrieves the result of the path-traversal.

      visit(TreeNode) must be called before calling this method; otherwise the behavior of this method is not defined.

      Returns:
      identity to be calculated by path-traversal

    • visit

      protected void visit(TreeNode<T> root)
      Executes the path-traversal algorithm on a specified binary tree.

      Algorithm: a straight forward recursion approach is RootToLeafPathsMaker.constructTreePaths(TreeNode, Path). This is a tail recursion which can be changed to an iterative algorithm (1st draft) as follows: 

       
 final Deque<TreeNode<T>> path = new ArrayDeque<>();
 final Deque<TreeNode<T>> stack = new ArrayDeque<>(Collections.singleton(root));

 while (!stack.isEmpty()) {
     final TreeNode<T> current = stack.pop();

     path.addLast(current);

     if (isLeaf(current)) {
         getPaths().add(new LinkedList<>(path));
         path.removeLast();
     }

     if (current.getRight() != null) {
         stack.push(current.getRight());
     }

     if (current.getLeft() != null) {
         stack.push(current.getLeft());
     }
 }
      This works for trees like 
           1
   /  \
  2   3
      but not 
            1
    /  \
   2   3
  / \   \
 4  5   6
      because we will get "1-2-3-6" as the last path. The path is not able to be updated to remove 2. To address that, we record parent of each node in a map as we traverse. For each node popping out of stack, we use this map to keep removing elements from path until we see the parent the current node. At this moment, path won't have 2 and 3 will get append to 1 correctly.
      Parameters:
      root - The root of the binary tree (cannot be null)
      See Also:

    • visitLeaf

      protected abstract void visitLeaf(Path<T> path)
      Performs action while path-traversal is visiting a leaf node.

      For example, while path-traversing the following tree 

            1
    /  \
   2   3
  / \   \
 4  5   6
      visitLeaf(Path) is called at node 4, 5, and 6.
      Parameters:
      path - A complete root-to-leaf path ending on the leaf being visited; for example, when calling visitLeaf(Path) at node 4, path is 1 -> 2 -> 4; at node 5, path is 1 -> 2 -> 5; at node 6, path is 1 -> 3 -> 6