Skip to content

Commit 3e0cfa5

Browse files
mitchellirvinmitchellirvin
committed
iluwatar#778 Implemented BSTIterator. Included comprehensive unit and integration tests. Refactored file structure to be friendly to future contributors with iterators of more data structures. Added JUnitPlatform to enable running test suite across all iterator implementations. Added README to /binarysearchtree to document what it does and how it works.
1 parent facb9e5 commit 3e0cfa5

17 files changed

Lines changed: 458 additions & 40 deletions

File tree

‎iterator/etc/bst.png‎

99.2 KB
Loading

‎iterator/etc/iterator.ucls‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
<?xml version="1.0" encoding="UTF-8"?>
22
<class-diagram version="1.1.8" icons="true" automaticImage="PNG" always-add-relationships="false" generalizations="true"
33
realizations="true" associations="true" dependencies="false" nesting-relationships="true">
4-
<class id="1" language="java" name="com.iluwatar.iterator.TreasureChest" project="iterator"
4+
<class id="1" language="java" name="com.iluwatar.iterator.list.TreasureChest" project="iterator"
55
file="/iterator/src/main/java/com/iluwatar/iterator/TreasureChest.java" binary="false" corner="BOTTOM_RIGHT">
66
<position height="124" width="195" x="1" y="237"/>
77
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -10,7 +10,7 @@
1010
<operations public="true" package="true" protected="true" private="true" static="true"/>
1111
</display>
1212
</class>
13-
<class id="2" language="java" name="com.iluwatar.iterator.Item" project="iterator"
13+
<class id="2" language="java" name="com.iluwatar.iterator.list.Item" project="iterator"
1414
file="/iterator/src/main/java/com/iluwatar/iterator/Item.java" binary="false" corner="BOTTOM_RIGHT">
1515
<position height="160" width="157" x="195" y="401"/>
1616
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -19,7 +19,7 @@
1919
<operations public="true" package="true" protected="true" private="true" static="true"/>
2020
</display>
2121
</class>
22-
<enumeration id="3" language="java" name="com.iluwatar.iterator.ItemType" project="iterator"
22+
<enumeration id="3" language="java" name="com.iluwatar.iterator.list.ItemType" project="iterator"
2323
file="/iterator/src/main/java/com/iluwatar/iterator/ItemType.java" binary="false" corner="BOTTOM_RIGHT">
2424
<position height="160" width="145" x="388" y="601"/>
2525
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -28,7 +28,7 @@
2828
<operations public="true" package="true" protected="true" private="true" static="true"/>
2929
</display>
3030
</enumeration>
31-
<interface id="4" language="java" name="com.iluwatar.iterator.ItemIterator" project="iterator"
31+
<interface id="4" language="java" name="com.iluwatar.iterator.list.ItemIterator" project="iterator"
3232
file="/iterator/src/main/java/com/iluwatar/iterator/ItemIterator.java" binary="false" corner="BOTTOM_RIGHT">
3333
<position height="106" width="131" x="236" y="237"/>
3434
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -37,7 +37,7 @@
3737
<operations public="true" package="true" protected="true" private="true" static="true"/>
3838
</display>
3939
</interface>
40-
<class id="5" language="java" name="com.iluwatar.iterator.TreasureChestItemIterator" project="iterator"
40+
<class id="5" language="java" name="com.iluwatar.iterator.list.TreasureChestItemIterator" project="iterator"
4141
file="/iterator/src/main/java/com/iluwatar/iterator/TreasureChestItemIterator.java" binary="false"
4242
corner="BOTTOM_RIGHT">
4343
<position height="160" width="323" x="236" y="37"/>

‎iterator/pom.xml‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,5 +48,11 @@
4848
<artifactId>junit-jupiter-params</artifactId>
4949
<scope>test</scope>
5050
</dependency>
51+
<dependency>
52+
<groupId>org.junit.platform</groupId>
53+
<artifactId>junit-platform-runner</artifactId>
54+
<version>1.2.0</version>
55+
<scope>test</scope>
56+
</dependency>
5157
</dependencies>
5258
</project>

‎iterator/src/main/java/com/iluwatar/iterator/binarysearchtree/BstIterator.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/**
2+
* The MIT License
3+
* Copyright (c) 2014-2016 Ilkka Seppälä
4+
*
5+
* Permission is hereby granted, free of charge, to any person obtaining a copy
6+
* of this software and associated documentation files (the "Software"), to deal
7+
* in the Software without restriction, including without limitation the rights
8+
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9+
* copies of the Software, and to permit persons to whom the Software is
10+
* furnished to do so, subject to the following conditions:
11+
*
12+
* The above copyright notice and this permission notice shall be included in
13+
* all copies or substantial portions of the Software.
14+
*
15+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16+
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17+
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18+
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19+
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21+
* THE SOFTWARE.
22+
*/
23+
package com.iluwatar.iterator.binarysearchtree;
24+
25+
import com.iluwatar.iterator.interfaces.Iterator;
26+
import java.util.ArrayDeque;
27+
28+
/**
29+
* This BstIterator iterates IN order. For example, given a BST with Integer values,
30+
* expect to retrieve TreeNodes according to the Integer's natural ordering (1, 2, 3...)
31+
* @param <T> This Iterator has been implemented with generic typing to allow traversal of TreeNodes of various types
32+
*/
33+
public class BstIterator<T> implements Iterator {
34+
35+
private ArrayDeque<TreeNode<T>> pathStack;
36+
37+
public BstIterator(TreeNode<T> root) {
38+
pathStack = new ArrayDeque<>();
39+
pushPathToNextSmallest(root);
40+
}
41+
42+
/**
43+
* This BstIterator manages to use O(h) extra space, where h is the height of the tree
44+
* It achieves this by maintaining a stack of the nodes to handle (pushing all left nodes first),
45+
* before handling self or right node
46+
* @param node TreeNode that acts as root of the subtree we're interested in.
47+
*/
48+
private void pushPathToNextSmallest(TreeNode<T> node) {
49+
while (node != null) {
50+
pathStack.push(node);
51+
node = node.getLeft();
52+
}
53+
}
54+
55+
/**
56+
* @return true if this iterator has a "next" element
57+
*/
58+
@Override
59+
public boolean hasNext() {
60+
return !pathStack.isEmpty();
61+
}
62+
63+
/**
64+
*
65+
* @return TreeNode next. The next element according to our in-order traversal of the given BST
66+
* @throws IllegalStateException if this iterator does not have a next element
67+
*/
68+
@Override
69+
public TreeNode<T> next() throws IllegalStateException {
70+
if (pathStack.isEmpty()) {
71+
throw new IllegalStateException();
72+
}
73+
TreeNode<T> next = pathStack.pop();
74+
pushPathToNextSmallest(next.getRight());
75+
return next;
76+
}
77+
78+
}

‎iterator/src/main/java/com/iluwatar/iterator/binarysearchtree/README.md‎

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
# BSTIterator
2+
An implementation of the Iterator design pattern, for the Binary Search Tree
3+
data structure. A great explanation of BSTs can be found in this [video tutorial](https://www.youtube.com/watch?v=i_Q0v_Ct5lY).
4+
5+
### What it Does
6+
This iterator assumes that the given binary search tree inserts nodes of smaller
7+
value to the left, and nodes of larger value to the right of current node. Accordingly,
8+
this iterator will return nodes according to "In Order" binary tree traversal.
9+
This means that given a binary search tree like the following, the iterator would
10+
return values in order: 1, 3, 4, 6, 7, 8, 10, 13, 14.
11+
12+
![BST](../../../../../../../etc/bst.png "Binary Search Tree")
13+
14+
### How It's Done
15+
**The trivial solution** to a binary search tree iterator would be to construct a List (or similar
16+
linear data structure) when you construct the BSTIterator. This would require traversing the entire
17+
BST, adding each node value to your list as you go. The downside to the trivial solution is twofold.
18+
You're front loading the work by requiring the BSTIterator's constructor to traverse the entire tree,
19+
and you're taking up more memory by maintaining (worst case) every node in the tree in a separate
20+
data structure. In Big O terms, here are the costs, where n is the number of nodes in the tree:
21+
* Constructor Run Time: O(n)
22+
* `next()` Run Time: O(1)
23+
* `hasNext()` Run Time: O(1)
24+
* Extra Space: O(n)
25+
26+
**A better solution** is to maintain _only_ the path to the next smallest node. For instance, given
27+
the BST above, when you first create your BSTIterator, instead of traversing the entire tree, you
28+
would navigate to the next smallest node (in this case, 1), pushing nodes onto a stack along the way.
29+
Your BSTIterator Constructor would look like:
30+
```
31+
private ArrayDeque<TreeNode> pathStack;
32+
33+
public BSTIterator(TreeNode root) {
34+
pathStack = new ArrayDeque<>();
35+
pushPathToNextSmallest(root);
36+
}
37+
38+
private void pushPathToNextSmallest(TreeNode node) {
39+
while (node != null) {
40+
pathStack.push(node);
41+
node = node.getLeft();
42+
}
43+
}
44+
```
45+
46+
After the constructor is called our BST, your `pathStack` would look like this:
47+
48+
1\
49+
3\
50+
8
51+
52+
This way, you're certain of what the next smallest node is because it lives on top of your path
53+
stack. In order to maintain the integrity of this path stack, when you call `next()` and pop a
54+
node off the stack, you must check to see if it has a right child. If it does, then you must follow the right
55+
child's path to the next smallest node (pushing onto your path stack as you go). Given our above example,
56+
calling `next()` on our BSTIterator twice would return node "3". Node "3" has a right child, indicating
57+
a path to a node smaller than 3's parent. In this case, you would push node "6" onto the stack,
58+
and node "4" onto the stack. `next()` would look like this:
59+
60+
```
61+
public TreeNode next() throws IllegalStateException {
62+
// If the user calls next() and hasNext() is false
63+
if (pathStack.isEmpty()) {
64+
throw new IllegalStateException();
65+
}
66+
TreeNode next = pathStack.pop();
67+
// follow right child to next smallest node
68+
pushPathToNextSmallest(next.getRight());
69+
return next;
70+
}
71+
```
72+
73+
**Key Concept:** The path to the smallest node of a given subtree is navigating straight to the
74+
leftmost node of that subtree.
75+
76+
In Big O terms, here are the costs for our improved solution, where h is the height of the tree:
77+
* Constructor Run Time: O(h)
78+
* `next()` Amortized Run Time: O(1)
79+
* `hasNext()` Run Time: O(1)
80+
* Extra Space: O(h)
81+
82+
As you can see, this solution more evenly distributes the work. It yields the same amortized
83+
runtime for `next()`, reduces the run time of the constructor, and uses less extra space.
84+
85+
86+

‎iterator/src/main/java/com/iluwatar/iterator/binarysearchtree/TreeNode.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/**
2+
* The MIT License Copyright (c) 2014-2016 Ilkka Seppälä
3+
*
4+
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
5+
* associated documentation files (the "Software"), to deal in the Software without restriction,
6+
* including without limitation the rights to use, copy, modify, merge, publish, distribute,
7+
* sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
8+
* furnished to do so, subject to the following conditions:
9+
*
10+
* The above copyright notice and this permission notice shall be included in all copies or
11+
* substantial portions of the Software.
12+
*
13+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14+
* NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15+
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
16+
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
17+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18+
*/
19+
package com.iluwatar.iterator.binarysearchtree;
20+
21+
/**
22+
* This TreeNode class allows for a generically typed value.
23+
* @param <T> generically typed to accept various data types for the val property
24+
*/
25+
public class TreeNode<T> {
26+
27+
private T val;
28+
private TreeNode<T> left;
29+
private TreeNode<T> right;
30+
31+
/**
32+
* Creates a TreeNode with a given value, and null children
33+
* @param val The value of the given node
34+
*/
35+
public TreeNode(T val) {
36+
this.val = val;
37+
this.left = null;
38+
this.right = null;
39+
}
40+
41+
T getVal() {
42+
return val;
43+
}
44+
45+
TreeNode<T> getLeft() {
46+
return left;
47+
}
48+
49+
void setLeft(TreeNode<T> left) {
50+
this.left = left;
51+
}
52+
53+
TreeNode<T> getRight() {
54+
return right;
55+
}
56+
57+
void setRight(TreeNode<T> right) {
58+
this.right = right;
59+
}
60+
61+
@Override
62+
public String toString() {
63+
return val.toString();
64+
}
65+
66+
}

‎iterator/src/main/java/com/iluwatar/iterator/interfaces/Iterator.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
* The MIT License Copyright (c) 2014-2016 Ilkka Seppälä
3+
*
4+
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
5+
* associated documentation files (the "Software"), to deal in the Software without restriction,
6+
* including without limitation the rights to use, copy, modify, merge, publish, distribute,
7+
* sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
8+
* furnished to do so, subject to the following conditions:
9+
*
10+
* The above copyright notice and this permission notice shall be included in all copies or
11+
* substantial portions of the Software.
12+
*
13+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14+
* NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15+
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
16+
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
17+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18+
*/
19+
package com.iluwatar.iterator.interfaces;
20+
21+
/**
22+
* Iterator interface to be implemented by iterators over various data structures
23+
* @param <T> generically typed for various objects
24+
*/
25+
public interface Iterator<T> {
26+
27+
boolean hasNext();
28+
29+
T next();
30+
}

iterator/src/main/java/com/iluwatar/iterator/App.java renamed to iterator/src/main/java/com/iluwatar/iterator/list/App.java

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,8 +20,9 @@
2020
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
2121
* THE SOFTWARE.
2222
*/
23-
package com.iluwatar.iterator;
23+
package com.iluwatar.iterator.list;
2424

25+
import com.iluwatar.iterator.interfaces.Iterator;
2526
import org.slf4j.Logger;
2627
import org.slf4j.LoggerFactory;
2728

@@ -30,7 +31,7 @@
3031
* The Iterator pattern is a design pattern in which an iterator is used to traverse a container and
3132
* access the container's elements. The Iterator pattern decouples algorithms from containers.
3233
* <p>
33-
* In this example the Iterator ({@link ItemIterator}) adds abstraction layer on top of a collection
34+
* In this example the Iterator ({@link Iterator}) adds abstraction layer on top of a collection
3435
* ({@link TreasureChest}). This way the collection can change its internal implementation without
3536
* affecting its clients.
3637
*

iterator/src/main/java/com/iluwatar/iterator/Item.java renamed to iterator/src/main/java/com/iluwatar/iterator/list/Item.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
2121
* THE SOFTWARE.
2222
*/
23-
package com.iluwatar.iterator;
23+
package com.iluwatar.iterator.list;
2424

2525
/**
2626
*

iterator/src/main/java/com/iluwatar/iterator/ItemIterator.java renamed to iterator/src/main/java/com/iluwatar/iterator/list/ItemIterator.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
2121
* THE SOFTWARE.
2222
*/
23-
package com.iluwatar.iterator;
23+
package com.iluwatar.iterator.list;
2424

2525
/**
2626
*

0 commit comments

Comments
 (0)