Skip to content

Instantly share code, notes, and snippets.

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/b8feda23a037109334e513952475415b to your computer and use it in GitHub Desktop.
Save jianminchen/b8feda23a037109334e513952475415b to your computer and use it in GitHub Desktop.
Binary search tree - inorder successor - more simple code
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinarySearchTreeSuccessor_mockingInterview
{
/// <summary>
/// binary search tree successor
/// June 28, 2017
/// </summary>
class Program
{
static void Main(string[] args)
{
var root = new Node(30);
root.Left = new Node(19);
root.Left.Parent = root;
root.Right = new Node(30);
root.Right.Parent = root;
root.Left.Left = new Node(15);
root.Left.Left.Parent = root.Left;
root.Left.Right = new Node(22);
root.Left.Right.Parent = root.Left;
var node22 = root.Left.Right;
node22.Left = new Node(21);
node22.Left.Parent = node22;
node22.Right = new Node(24);
node22.Right.Parent = node22;
var testcase1 = FindInOrderSuccessor(root.Left.Left);
Debug.Assert(testcase1.Value == 19);
var testcase2 = FindInOrderSuccessor(root.Left);
Debug.Assert(testcase2.Value == 21);
var testcase3 = FindInOrderSuccessor(node22.Right);
Debug.Assert(testcase3.Value == 30);
}
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 v)
{
Value = v;
}
}
// given 15, find 19
// test case 2: given node 24
// test case 3: given node 35
// test case 4: given node 19
// test case 5: given node 30
// test case 6: given node 21
// time complexity - BST O(logN) - O(N) - space - linked list O(N)
static Node FindInOrderSuccessor(Node inputNode)
{
// your code goes here
if (inputNode == null)
{
return null;
}
// assume that node at least has one child
bool hasRightChild = inputNode.Right != null; // false, false
if (hasRightChild)
{
return getMinimum(inputNode.Right); // ? node 22 , return node 21
}
// now we can assume that the node does not have right child
// find parent node which is bigger than givenNode
var givenValue = inputNode.Value; // 15, 24, 35
var iterate = inputNode;
while (iterate.Parent != null && iterate.Parent.Value < givenValue) // 19 > 15, 22 < 24, 30 > 24
{
iterate = iterate.Parent; // node 22, node 19
}
return iterate.Parent;
}
/// <summary>
///
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
private static Node getMinimum(Node root)
{
var minimum = root; // node 22
while (minimum.Left != null)
{
minimum = minimum.Left; // node 21
}
return minimum; // return node 21
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment