binary search tree in order successor mock interview - Jan. 20, 2018

bstInorder Successor mock Jan20 2018 analysis

// Given the node with value 14, its inorder successor is 20; given the node with value 25, its inorder successor is null. given the node with value 9, its inorder successor is 11.
  
  internal class TreeNode
        {
            public int      Value { get; set; }
            public TreeNode Left  { get; set; }
            public TreeNode Right { get; set; }

            public TreeNode(int number)
            {
                Value = number;
            }
        }
        
    20 
   /  \
  9     25
 / \
 5  12 
    /\
  11   14
  
  
  5  9  11 12 14 20 25
  
TreeNode FindLeastChild(TreeNode cur) {
  while (cur.Left != null) {
    cur = cur.Left;
  }
  return cur;
}

TreeNode FindBinarySearchTreeInOrderSuccessor(TreeNode root, TreeNode givenNode)
{
  TreeNode parent = null;
  TreeNode cur = root;
  while (cur && cur.Value != givenNode.Value) {
    if (cur.Value > givenNode.Value) {
      parent = cur;
      cur = cur.Left;
    } else {
      cur = cur.Right;
    }
  }
  if (cur == null) {
    // givenNode is not in the tree!
    return null;
  }
  
  if (cur.Right != null) {
    parent = cur.Right;
  }
  
  return FindLeastChild(parent);
}