Package io.openml.gearbox.binarytree.pathvisitor

Class RootToLeafPathsMaker<T>

java.lang.Object

io.openml.gearbox.binarytree.pathvisitor.AbstractRootToLeafPathVisitor<T,List<Path<T>>>

io.openml.gearbox.binarytree.pathvisitor.RootToLeafPathsMaker<T>

Type Parameters:

T - The type of value store in the node of the original tree

public class RootToLeafPathsMaker<T>
extends AbstractRootToLeafPathVisitor<T,List<Path<T>>>

RootToLeafPathsMaker constructs and maintains an immutable list of root-to-leaf paths of a binary tree.

For example, all root-to-leaf paths of

      1
    /  \
   2   3
  / \   \
 4  5   6
 

are [1 -> 2 -> 4 -> x, 1 -> 2 -> 5 -> x, 1 -> 3 -> 6 -> x]

All paths are constructed in O(n * h) time and O(n) space complexity, where n is the number of nodes in the binary tree and h the height of the binary tree

Constructor Summary

Constructors

Constructor	Description
RootToLeafPathsMaker()

Method Summary

Modifier and Type	Method	Description
static <T> RootToLeafPathsMaker<T>	constructFor(TreeNode<T> root)	Constructs all root-to-leaf paths of a specified binary tree.
protected void	constructTreePaths(TreeNode<T> root, Path<T> path)	Deprecated. recursion is inefficient on large tree
List<Path<T>>	getAllPaths()	Returns an immutable view of all the root-to-leaf paths of the wrapped tree.
List<Path<T>>	getVisitResult()	Retrieves the result of the path-traversal.
protected void	visitLeaf(Path<T> path)	Performs action while path-traversal is visiting a leaf node.

Methods inherited from class io.openml.gearbox.binarytree.pathvisitor.AbstractRootToLeafPathVisitor

visit

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

RootToLeafPathsMaker

public RootToLeafPathsMaker()

Method Details

constructFor

public static <T> RootToLeafPathsMaker<T> constructFor(TreeNode<T> root)

Constructs all root-to-leaf paths of a specified binary tree.

Type Parameters:

T - The type of value store in the node of the original tree

Parameters:

root - The root of the binary tree

Returns:

a new RootToLeafPathsMaker instance.

Throws:

NullPointerException - if root is null

getAllPaths

public List<Path<T>> getAllPaths()

Returns an immutable view of all the root-to-leaf paths of the wrapped tree.

This method returns the same result as getVisitResult().

Returns:

a list of paths, each follows the root-to-leaf order

getVisitResult

public List<Path<T>> getVisitResult()

Description copied from class: AbstractRootToLeafPathVisitor

Retrieves the result of the path-traversal.

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

Specified by:

getVisitResult in class AbstractRootToLeafPathVisitor<T,List<Path<T>>>

Returns:

identity to be calculated by path-traversal

visitLeaf

protected void visitLeaf(Path<T> path)

Description copied from class: AbstractRootToLeafPathVisitor

Performs action while path-traversal is visiting a leaf node.

For example, while path-traversing the following tree

      1
    /  \
   2   3
  / \   \
 4  5   6
 

AbstractRootToLeafPathVisitor.visitLeaf(Path) is called at node 4, 5, and 6.

Specified by:

visitLeaf in class AbstractRootToLeafPathVisitor<T,List<Path<T>>>

Parameters:

path - A complete root-to-leaf path ending on the leaf being visited; for example, when calling AbstractRootToLeafPathVisitor.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

constructTreePaths

@Deprecated
protected void constructTreePaths(TreeNode<T> root,
 Path<T> path)

Deprecated.

recursion is inefficient on large tree

Computes all root-to-leaf paths of a binary tree recursively.

Parameters:

root - the root of the binary tree

path - a path under construction, caller of this recursive method should initially pass an empty path argument