Binary search tree inorder successor - May 20, 2017

BST_inorderSuccessor_May202017.cs

using System;

class Solution
{
  class Node
  {
    public int value {get; set;}
    public Node left {get; set;}
    public Node right {get; set;}
    public Node parent{get; set;}
    
    public Node(int number)
    {
      value = number; 
    }
  }

  static Node findInOrderSuccessor(Node inputNode)
  {
    // your code goes here
    if(inputNode == null) return null; 
    
    // assume node is not null
    bool haveRightChild = inputNode.right != null;
    if(haveRightChild)
    {
      return findSmallestNode(inputNode.right); 
    }
    else 
    {
      Node current = inputNode; 
      while(current.parent != null  && current.parent.value < current.value)
      {
        current = current.parent; 
      }
      
      return current.parent;
    }    
  }
  
  private static Node findSmallestNode(Node root)
  {
    if(root.left == null) return root;
    return findSmallestNode(root.left); 
  }

  static void Main(string[] args)
  {
    // test findInOrderSuccessor here
    
    Node root = new Node(20); 
    root.left = new Node(9); 
    root.left.parent = root; 
    
    root.left.left = new Node(5); 
    root.left.left.parent = root.left; 
    
    root.left.right = new Node(12); 
    root.left.right.parent = root.left; 
    
    root.left.right.left = new Node(11);
    root.left.right.left.parent = root.left.right; 
    
    var result = findInOrderSuccessor(root.left.right); 
    Console.WriteLine(result.value); 
    
    var result2 = findInOrderSuccessor(root.left); 
    Console.WriteLine(result2.value); 
  }
}

// BST, left node < root.value, rigt.value > root.Value
// 20, right child, 25 > 20, your right subtree -> minimum 
// node 9, "11, 12, 14", -> left -> left
// the case if you have right node

// you are the node 11, you do not have right child; then you go back to your parent
// 12, 9 , basically, I found my parent until the node value is bigger than myself, it is my successor
// 14, 12 < 14, 9 vs 14, 9 -> 20 > 14, I found 14's successor is 20