Largest smaller binary search tree key -

largestSmallerBSTKey_peerCode_reviewed.cs

using 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)
  {
    if (rootNode == null)
      return -1;
    
    if (rootNode.Key < num)
    {
      var r = findLargestSmallerKey(rootNode.right, num);
      if (r != -1)
        return r;
      else
        return rootNode.Key;
    } 
    else
    { 
      return findLargestSmallerKey(rootNode.left, num);
    }
  }
  
  /*
      
      2
     / \   num = 3 -> 2
    1   5  num = 7 -> 5
           num = 2 -> 1
      rootNode = 2 num = 3
      
  */

  static void Main(string[] args)
  {

  }
}

/*
  Assumptions:
    all keys in the tree are nonnegative
    strictly less than (no equal to)
    if no smaller key return -1
    
      2
     / \   num = 3 -> 2
    1   5  num = 7 -> 5
           num = 2 -> 1           
           
      2   num = 1 -> -1         
      
   Overview:
      recursive approach
      base case: comparing against a node that has no children
                 if key is smaller than num
                    return num
                 else
                    return -1
                    
      standard binary search tree traversal for nodes with children
      
      worst case: O(N) expected case: O(logN)
      size complexity: recrusive so depth of the recursive tree <- potentially improve with iterative
   */