Open
Description
Context
Common operations surrounding BST's are retrieving Predecessor & Successor Successors.
The definitions of both terms are as follows:
Successor
The Successor can be thought of as the smallest value greater than the value of the given node.
E.G. Given a tree that looks like:
graph TB;
A((8))-->B((3))
A-->C((10))
B-->D((1))
B-->E((6))
C-->F((9))
C-->G((14))
E-->H((4))
E-->I((7))
The Successor of 3
is 4
.
Predecessor
The Predecessor can be thought of as the greatest value less than the value of the given node.
E.G Given a tree that looks like:
graph TB;
A((8))-->B((3))
A-->C((10))
B-->D((1))
B-->E((6))
C-->F((9))
C-->G((14))
E-->H((4))
E-->I((7))
The Predecessor of 8
is 7
.
What We Need To Do
Successor & Predecessor retrieval methods should implemented as part of the BinarySearchTree
trait and implemented within RecursiveBST
& IterativeBST