Largest smaller BST key - mock interview May 7 2018 - write a recursive solution 8:00 PM

LargestSmallerBSTKey_recursiveSolution.cs

using System;

class Solution
{
  public class Node
  {
    public int key;
    public Node left;
    public Node right;
    public Node parent;
  }    
    
  ///  given number = 17, 
  ///  given number = 13, 
  ///  given number = 27
   public static int findLargestSmallerKeyRecursive(Node rootNode, int num) // num = 17
  {
    if(rootNode == null || num < 0) // false
      return -1; 
    
    if(rootNode.key < num)  // root 20, num = 17 
    {
      return Math.Max(rootNode.key, findLargestSmallerKeyRecursive(rootNode.right, num));
    }
    else
      return findLargestSmallerKeyRecursive(rootNode.left, num);
    
  }

  static void Main(string[] args)
  {

  }
}

/*
keywords: 
given a root, Binary Search Tree, given a num, 
ask: find largest smaller key that is smaller than num
constraint: element - nonnegative >= 0
  
  brute force solution, traversal -> in ascending order 
  Time complexity: O(n) - size of tree 
Solution:
either go right or go left depending on element value
  loop -> 
  if elment value < num 
  then 
     go right
     largestValue = element value
  else
    go left 
    
    Space complexity: O(1)
    Time complexity: O(logn) -> O(n)
    
  May 7, 2018  8:30 PM - 8:52 PM 
  */