1using System;

class Solution
{
  public class Node
  {
    public int key;
    public Node left;
    public Node right;
    public Node parent;
  }

  public static int findLargestSmallerKey(Node rootNode, int num)  // given 17, find 14
  {
    if(rootNode == null) // false
    {
      return -1;
    }

    var visitNode = rootNode; // 20
    var largestSmaller = -1;

    while(visitNode != null) // true
    {
      if (visitNode.key < num) // 20 < 17 false, 9 < 17 , 12 < 17 , 14 < 17
      {
        largestSmaller = visitNode.key; // 8 , 12, 14

        visitNode = visitNode.right; // node 12, node 14, null
      }
      else
      {
        visitNode = visitNode.left; // node 9
      }
    }

    return largstSmaller; // n14
  }

  static void Main(string[] args)
  {

  }
}

/*

14 --> 12
5 9 11 12 14 20 25
              |

             given 17, find larest smaller BST key
          14
          left side ->
          20 > 17
   |
   9  < 17 , 9 largest, I am not sure

   go to right
     |
     12 < 17

        14 < 17

        14.right == null -> largest one is 14


*/