• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
daily pastebin goal
34%
SHARE
TWEET

# Untitled

a guest Feb 23rd, 2018 67 Never
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.

Top