Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Inorder successor of binary search tree - need to compile.
using System;
class Solution
{
class Node
{
public int value;
public Node left;
public Node right;
public Node parent;
}
// given 5, find 9
// test case 2: given node 14
// test case 3: give node 25
// test case 4: given node 9
// test case 5: given node 20
// test case 6: given node 11
// 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 12 , return node 11
}
else
{
// find parent node which is bigger than givenNode
var givenValue = inputNode.value; // 5, 14, 25
var iterate = inputNode;
while(iterate.parent != null && iterate.parent.value < givenValue) // 9 > 5, 12 < 14, 20 > 14
{
iterate = iterate.parent; // node 12, node 9
}
return iterate.parent;
/*
// uttermost parent node, iterate node has no parent node
if(iterate.parent != null && iterate.parent.value > givenValue)
{
return iterate.parent; // return node 9 , return node 20, return 12
}
else
{
return null; // return null,
}
*/
}
}
private static Node getMinimum(Node root)
{
var minimum = root; // node 12
while(minimum.left != null)
{
minimum = minimum.left; // node 11
}
return minimum; // return node 11
}
static void Main(string[] args)
{
// test findInOrderSuccessor here
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.