daily pastebin goal
34%
SHARE
TWEET

Untitled

a guest Feb 23rd, 2018 67 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. using System;
  2.  
  3. class Solution
  4. {
  5.   public class Node
  6.   {
  7.     public int value;
  8.     public Node left;
  9.     public Node right;
  10.     public Node parent;
  11.    
  12.     public Node(int number)
  13.     {
  14.       value = number;
  15.     }
  16.   }
  17.  
  18.   public static Node findInOrderSuccessor(Node inputNode)
  19.   {
  20.     if(inputNode == null)
  21.     {
  22.       return null;
  23.     }
  24.    
  25.     if(inputNode.right != null)
  26.     {
  27.       // find leftmost child node
  28.       var leftmost = inputNode.right;
  29.       while(leftmost.left != null)
  30.       {
  31.         leftmost = leftmost.left;
  32.       }
  33.      
  34.       return leftmost; // smallest one in right subtree
  35.     }
  36.     else
  37.     {
  38.       var upward = inputNode.parent;
  39.       while(upward != null && upward.value < inputNode.value)
  40.       {
  41.         upward = upward.parent;
  42.       }
  43.      
  44.       return upward; // return null or node with value bigger than given value
  45.     }
  46.   }
  47.  
  48.   static void Main(string[] args)
  49.   {
  50.     var node20 = new Node(20);
  51.     var node9  = new Node(9);
  52.     var node25 = new Node(25);
  53.    
  54.     node20.left = node9;
  55.     node20.right = node25;
  56.    
  57.     node9.parent = node20; // ok
  58.     node25.parent = node20;
  59.    
  60.     var node12 = new Node(12);
  61.     node9.right = node12;
  62.    
  63.     node12.parent = node9; // ok
  64.    
  65.    
  66.     var node11 = new Node(11);
  67.     node11.parent = node12;
  68.     node12.left = node11;
  69.    
  70.     var node14 = new Node(14);
  71.     node14.parent = node12;  // ok
  72.     node12.right = node14;
  73.    
  74.     var successor = findInOrderSuccessor(node14);
  75.     Console.WriteLine("14's succcessor is " + successor.value);
  76.    
  77.     var successor2 = findInOrderSuccessor(node9);
  78.     Console.WriteLine("9's succcessor is " + successor2.value);    
  79.   }
  80. }
  81.  
  82.  
  83. /*
  84. 5 9 11 12 14 20 25
  85.  
  86.   given input node 9, the successor is 11.
  87.   14, find 20
  88.  
  89.   first check right subtree
  90.   second check parent node, parent node
  91.   */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top