Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created July 22, 2017 21:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/eee4a66fbe45111429b0c18df574fa48 to your computer and use it in GitHub Desktop.
Save jianminchen/eee4a66fbe45111429b0c18df574fa48 to your computer and use it in GitHub Desktop.
Largest smaller key value in binary search tree - code review - July 22, 2017
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LargestSmallerBinarySearchTreeValue
{
/// <summary>
/// code review July 22, 2017
/// </summary>
public class Node{
public int Key {get; set;}
public Node Left {get; set;}
public Node Right {get; set;}
}
class Program
{
static void Main(string[] args)
{
}
/// <summary>
/// get largest smaller key in binary search tree
/// assuming that all numbers in the tree are nonnegative integer.
/// </summary>
/// <returns></returns>
public static int GetLargestSmallerBSTKey(Node root, int number)
{
if(root == null)
{
return -1;
}
var visit = root.Key;
bool searchIsSmaller = number <= visit;
if(searchIsSmaller)
{
return GetLargestSmallerBSTKey(root.Left, number);
}
// assuming that visit < number
var candiate = visit;
return Math.Max(candiate, GetLargestSmallerBSTKey(root.Right, number));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment