navigating binary search tree we begin by demonstrating that binary search tree hierarchically represents the sorted order of its keys in particularthe structural property regarding the placement of keys within binary search tree assures the following important consequence regarding an inorder traversal (section of the tree proposition an inorder traversal of binary search tree visits positions in increasing order of their keys justificationwe prove this by induction on the size of subtree if subtree has at most one itemits keys are trivially visited in order more generallyan inorder traversal of (sub)tree consists of recursive traversal of the (possibly emptyleft subtreefollowed by visit of the rootand then recursive traversal of the (possibly emptyright subtree by inductiona recursive inorder traversal of the left subtree will produce an iteration of the keys in that subtree in increasing order furthermoreby the binary search tree propertyall keys in the left subtree have keys strictly smaller than that of the root thereforevisiting the root just after that subtree extends the increasing order of keys finallyby the search tree propertyall keys in the right subtree are strictly greater than the rootand by inductionan inorder traversal of that subtree will visit those keys in increasing order since an inorder traversal can be executed in linear timea consequence of this proposition is that we can produce sorted iteration of the keys of map in linear timewhen represented as binary search tree although an inorder traversal is typically expressed using top-down recursionwe can provide nonrecursive descriptions of operations that allow more finegrained navigation among the positions of binary search relative to the order of their keys our generic binary tree adt from is defined as positional structureallowing direct navigation using methods such as parent( )left( )and right(pwith binary search treewe can provide additional navigation based on the natural order of the keys stored in the tree in particularwe can support the following methodsakin to those provided by positionallist (section first)return the position containing the least keyor none if the tree is empty last)return the position containing the greatest keyor none if empty tree before( )return the position containing the greatest key that is less than that of position ( the position that would be visited immediately before in an inorder traversal)or none if is the first position after( )return the position containing the least key that is greater than that of position ( the position that would be visited immediately after in an inorder traversal)or none if is the last position