Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Binary search tree inorder successor - May 20, 2017
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
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.