content: package by.andd3dfx.tree;
  
  /**
   * <pre>
   * We have binary search tree:
   *
   * public interface Node {
   *    Node getParent();
   *    Node getLeft();
   *    Node getRight();
   * }
   *
   * If item.value >= node.value - it belongs to right branch,
   * If item.value < node.value - it belongs to left branch
   *
   * Write method next() to determine next node:
   * public Node next(Node node) {
   *     ...
   * }
   * <pre/>
   *
   * @see <a href="https://youtu.be/qg0b9f8wGCg">Video solution</a>
   */
  public class NextNodeForBinarySearchTree {
  
      public interface Node {
          Node getParent();
  
          Node getLeft();
  
          Node getRight();
      }
  
      public static Node next(Node node) {
          if (node.getRight() != null) {
              // Find left-most node of right child of 'node'
              return findLeftMostNode(node.getRight());
          }
          // Go up by parents, until some transition will be left child of some node. If so - stop.
          return findParentWithLeftTransition(node);
      }
  
      private static Node findLeftMostNode(Node node) {
          if (node.getLeft() == null) {
              return node;
          }
          return findLeftMostNode(node.getLeft());
      }
  
      private static Node findParentWithLeftTransition(Node node) {
          if (node.getParent() == null) {
              return node;
          }
          if (node.getParent().getLeft() == node) {
              return node.getParent();
          }
          return findParentWithLeftTransition(node.getParent());
      }
  }
  