Class RootToLeafPathsMaker<T>

java.lang.Object

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

io.openml.gearbox.algorithms.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 AbstractRootToLeafPathVisitor

visit

Methods inherited from class 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