Created
June 28, 2017 18:18
-
-
Save jianminchen/b8feda23a037109334e513952475415b to your computer and use it in GitHub Desktop.
Binary search tree - inorder successor - more simple code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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