Package Struct
Class BSTNode<T extends Comparable<T>>
java.lang.Object
Struct.BSTNode<T>
- Type Parameters:
T
- The type of values stored in the BST. Must implementComparable<T>
.
Represents a node in a binary search tree (BST) for elements of a comparable type.
This class provides basic BST operations including insertion and traversal.
- Since:
- 1.0
- Version:
- 1.0
- Author:
- Sahasrad Chippa
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription<R> R
accumulateInOrder
(R initial, Function<BSTNode<T>, R> function, BiFunction<R, R, R> accumulator) Aggregates results across the BST nodes using an inorder traversal.<R> R
accumulatePostOrder
(R initial, Function<BSTNode<T>, R> function, BiFunction<R, R, R> accumulator) Aggregates results across the BST nodes using a postorder traversal.<R> R
accumulatePreOrder
(R initial, Function<BSTNode<T>, R> function, BiFunction<R, R, R> accumulator) Aggregates results across the BST nodes using a preorder traversal.void
Adds a node to the correct position in the subtree.void
executeInOrder
(Consumer<BSTNode<T>> action) Executes a consumer function on each node in the BST following an inorder traversal.void
executePostOrder
(Consumer<BSTNode<T>> action) Executes a consumer function on each node in the BST following a postorder traversal.void
executePreOrder
(Consumer<BSTNode<T>> action) Executes a consumer function on each node in the BST following a preorder traversal.Constructs a list of node values following inorder traversal of the BST.Constructs a list of node values following postorder traversal of the BST.Constructs a list of node values following preorder traversal of the BST.
-
Field Details
-
left
This node's left child node, or null if not present. -
right
This node's right child node, or null if not present. -
val
This node's store value
-
-
Constructor Details
-
BSTNode
Initializes a BST node with the specified value.- Parameters:
val
- The value for this node.
-
-
Method Details
-
add
Adds a node to the correct position in the subtree. Uses T's compareTo method to determine the correct position in the BST. Duplicate values are added to the left subtree. Runs inO(log(n))
assuming the compare operation runs inO(1)
.- Parameters:
node
- The node to add.
-
toPreorderList
-
toInorderList
-
toPostorderList
-
executePreOrder
-
executeInOrder
-
executePostOrder
-
accumulatePreOrder
public <R> R accumulatePreOrder(R initial, Function<BSTNode<T>, R> function, BiFunction<R, R, R> accumulator) Aggregates results across the BST nodes using a preorder traversal. Uses a mapperFunction<BSTNode -> R>
and accumulatingBiFunction<(R, R) -> R>
- Type Parameters:
R
- The result type.- Parameters:
initial
- The initial value for accumulation.function
- A function to apply to each node, which generates a result of type R.accumulator
- A function that combines two results of type R.- Returns:
- The accumulated result after processing all nodes.
Runs in
O(n)
assuming the provided function runs inO(1)
.
-
accumulateInOrder
public <R> R accumulateInOrder(R initial, Function<BSTNode<T>, R> function, BiFunction<R, R, R> accumulator) Aggregates results across the BST nodes using an inorder traversal. Uses a mapperFunction<BSTNode -> R>
and accumulatingBiFunction<(R, R) -> R>
- Type Parameters:
R
- The result type.- Parameters:
initial
- The initial value for accumulation.function
- A function to apply to each node, which generates a result of type R.accumulator
- A function that combines two results of type R.- Returns:
- The accumulated result after processing all nodes.
Runs in
O(n)
assuming the provided function runs inO(1)
.
-
accumulatePostOrder
public <R> R accumulatePostOrder(R initial, Function<BSTNode<T>, R> function, BiFunction<R, R, R> accumulator) Aggregates results across the BST nodes using a postorder traversal. Uses a mapperFunction<BSTNode -> R>
and accumulatingBiFunction<(R, R) -> R>
- Type Parameters:
R
- The result type.- Parameters:
initial
- The initial value for accumulation.function
- A function to apply to each node, which generates a result of type R.accumulator
- A function that combines two results of type R.- Returns:
- The accumulated result after processing all nodes.
Runs in
O(n)
assuming the provided function runs inO(1)
.
-