Back>
In order to change the structure of the tree, there is no other place better than the current node. Current node is the edge when change happens. Here you have visited the left branch, you know the current node is above them, the right branch hasn't been visited yet, but you know they will all be larger.
With these special knowledge at the current node, we can solve many problem related to edge detection and tree structure change with in-order traversal.
For example,
To find the first node with value above K in a binary search tree, we are detecting the edge between smaller than k to larger than k. If we in-order traversal the tree, we are visiting the nodes from smaller to larger, sooner or later we will find the edge.
BTree.java
BTreePrinter.java
EdgeFindOne.java
EdgeFindOneTest.java
