Smallest number in BST which is greater than or equal to N

Question 1

Given a Binary Search Tree and a number N, the task is to find the
smallest number in the binary search tree that is greater than or
equal to N. Print the value of the element if it exists otherwise
print -1.

Please review the code, the unit tests are just for the demo. please comment about performance thanks.

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// <summary>
    /// https://www.geeksforgeeks.org/smallest-number-in-bst-which-is-greater-than-or-equal-to-n/
    /// </summary>
    [TestClass]
    public class SamllestNumberBstGreatherThanOrEqualToN
    {
        [TestMethod]
        public void SmallestNumberBstGreatherThanOrEqualToNTest()
        {
            BstNode root = new BstNode(19 );
            BstNode left = new BstNode(7);
            BstNode right = new BstNode(21);
            root.Left = left;
            root.Right = right;
            BstNode leftLeft = new BstNode(3);
            BstNode leftRight = new BstNode(11);
            BstNode leftRightLeft = new BstNode(9);
            BstNode leftRightRight = new BstNode(14);
            root.Left.Left = leftLeft;
            root.Left.Right = leftRight;
            root.Left.Right.Left = leftRightLeft;
            root.Left.Right.Right = leftRightRight;
            int result = SmallestNumberGratherThanOrEqual(root, 20);
            Assert.AreEqual(21, result);
        }

        [TestMethod]
        public void SmallestNumberBstGreatherThanOrEqualToNTest2()
        {
            /*    19 
        /     
       7     21 
     /    
    3     11 
         /    
         9    14 
          */

            BstNode root = new BstNode(19);
            root = root.Add(root, 7);
            root = root.Add(root, 3);
            root = root.Add(root, 11);
            root = root.Add(root, 9);
            root = root.Add(root, 13);
            root = root.Add(root, 21);
            int result = SmallestNumberGratherThanOrEqual(root, 18);
            Assert.AreEqual(19, result);
        }

        private int SmallestNumberGratherThanOrEqual(BstNode root, int num)
        {
            int smallest = -1;
            while (root != null)
            {
                if (root.Value >= num)
                {
                    smallest = root.Value;
                    root = root.Left;
                }
                else
                {
                    root = root.Right;
                }
            }
            return smallest;
        }
    }
}

here is also the BST class

public class BstNode
{
    public int Value;
    public BstNode Left;
    public BstNode Right;
    public BstNode Parent;

    public BstNode(int keyt)
    {
        Value = keyt;
    }

    public BstNode Add(BstNode node , int key)
    {
        if (node == null)
        {
            return new BstNode(key);
        }
        if (node.Value < key)
        {
            node.Right = Add(node.Right, key);
        }
        else
        {
            node.Left = Add(node.Left, key);
        }
        return node;
    }

}

Question 2

`SmallestNumberGratherThanOrEqual`

This looks mostly fine to me. I can’t think how else to implement it, since you can’t really separate the ‘finding smallest’ bit from the ‘finding where num would go’ bit.

The method should probably be public and static.
The spec does say a number N… but oh well. root is fine as the parameter name, but it quickly becomes misleading, as it ceases to be the root node pretty quickly.
It’s iterative, which makes me happy.

Since I have so little to say about the code in question…

`BstNode.Add(BstNode, int)`

Why does Add take a BstNode as a parameter?!?!?!?1 Either it should be an instance method and operate on itself, or it should be static and operate on the parameter. The problem here is both conceptual and technical, as it makes no sense to ask a BstNode to operate on another BstNode, and it means that both nodes are in scope, so you might use the wrong one by mistake. I often have an instance method call a private static method simply to avoid this (e.g. when calling something iterative which will ‘change’ the parameter as it goes).
This is odd:
```
if (node == null)
{
    return new BstNode(key);
}
```
This bit doesn’t actually add anything to anything – despite being in a method called Add – and is liable to cover-over a bug elsewhere which passes this method a null. Even worse, a null goes in, and something strange but not null comes out, which means the bug is likely to go even further now that there is some actual state going around.

I can see why it’s there (it’s part of the recursive method), but this sort of thing should not be public. Better would be to make this method private (and perhaps static and iterative as discussed above), and call it from another Add method which throws on null. This way, the specifics of your implementation of Add will not leak into the public API, and you can instead provide helpful error messages. You could also remove the return value, which is meaningless and just adds more confusion for the consumer.
Channelling t3chb0t for a moment… he might say that finding the base node and adding to it are different concerns, and that you should write one private method to find the node to add to, and call it from another which then does the adding. Such a method could not, however, be directly exploited to find the solution to the problem unless it was implemented in such a way that is basically did solve the problem, which is a bit of a shame.
As always, inline documentation (///) would be nice on this public method.

other `BstNode` stuff

keyt is a bit of an odd name.
Parent is never set. This is clearly an error and would make me as a consumer very sad if I’d designed my code around the assumption that I can access the parent of a BstNode and then discovered that I can not.
All the members are public fields: perhaps this is an attempt to avoid the overhead of getters? If so, don’t worry about that cost: they are usually optimized away completely for non-virtual properties (at least, whenever I look for them they don’t seem to be there).

I’d have Left and Right as public { get; private set; }. Parent and Value can be readonly if the tree if nodes are never removed from the tree. Indeed, for an ‘add-only’ tree, I’d be inclined to have the setters on Left and Right check that they are not overwriting anything. This would break the first test method, but frankly it’s horrifying and ought to be rewritten.
Passing BstNode around is fine if everything knows that it is a tree, but really you should have a BinarySearchTree class which encapsulates these nodes, as it is meaningless and dangerous to operate on them independently (e.g. if you call Add on a child node you may end up with a mal-formed tree): nobody should have write-access to BstNode except BinaryNodeTree. Doing so would require exposing methods to traverse the tree without allowing modifications, so that you can still write the specified search outside of the BinarySearchTree class. This also gives a nice solution to the root parameter name problem.

Generics

If it weren’t for the really horrible spec (-1 is a perfectly valid number, it should not be used as output here) I’d suggest this should be generic. Performance might suffer (depening on how you facilitate comparisons), but a generic solution is always nice: you can write a concrete version for int if the performance isn’t good enough later.

Performance

I don’t know anything about binary trees, but this is a very simple non-self-balancing implementation, and has a worst-case lookup time of O(n). A self-balancing tree (such as a Red-Black Tree (there are others) can guarantee logarithmic lookup time, at the cost of a more complicated data-structure and higher and the overheads which come with it. (This doesn’t, however, change how you would implemented the specification, as it assumes a binary tree and doesn’t ask you to modify it).

Boring stuff

I’d appreciate a few more empty lines to break the code up a bit, e.g. before the while, between all those ifs in Add, and before the returns.

SmallestNumberGratherThanOrEqual

BstNode.Add(BstNode, int)

other BstNode stuff