Test Qu: Some Binary Search Tree Illustrations

The following was toss together for the sake of coding up example questions  (no testing code written because I would prefer to code up a red-black implementation and that’s an exercise). See one of many examples on the web.

 

Code Snippet

1. using System;
2. using System.Collections.Generic;
3. using System.Data;
4. using System.Linq;
5. using System.Text;
6.  
7. namespace ConsoleApplication1
8. {
9.   public class BSTNode
10.   {
11.     /// <summary>
12.     /// Low Value
13.     /// </summary>
14.     public BSTNode LeftNode { get; set;}
15.     /// <summary>
16.     /// Low Value
17.     /// </summary>
18.     public BSTNode RightNode { get; set; }
19.     /// <summary>
20.     /// Value or Object
21.     /// </summary>
22.     public int Value { get; set; }
23.     public object Object { get; set; }
24.   }
25.   public class BinarySearchTree
26.   {
27.     private BSTNode _Root;
28.     public BinarySearchTree(BSTNode root)
29.     {
30.       _Root = root;
31.     }
32.     public BSTNode ExactFind(int lookupvalue)
33.     {
34.       if (_Root == null)
35.       {
36.         return null;
37.       }
38.       var active = _Root;
39.       while (active != null)
40.       {
41.         if (active.Value == lookupvalue)
42.         {
43.           break;
44.         }
45.         if (active.Value > lookupvalue)
46.         {
47.           active = active.LeftNode;
48.         }
49.         else // Must be <, no need to test
50.         {
51.           active = active.RightNode;
52.         }
53.       }
54.       return active;
55.     }
56.     public BSTNode MinValue()
57.     {
58.       if (_Root == null)
59.       {
60.         return null;
61.       }
62.        var active = _Root;     
63.       while (active.LeftNode != null)
64.       {
65.         active = active.LeftNode;
66.       }
67.       return active;
68.     }
69.     public BSTNode MaxValue()
70.     {
71.       if (_Root == null)
72.       {
73.         return null;
74.       }
75.       var active = _Root;
76.       while (active.RightNode != null)
77.       {
78.         active = active.RightNode;
79.       }
80.       return active;
81.     }
82.  
83.     public BSTNode NextNode(BSTNode node)
84.     {
85.       if (node == null)
86.       {
87.         return MinValue();
88.       }
89.       return NextNode(node.Value);
90.     }
91.  
92.     public BSTNode NextNode(int lookupvalue)
93.     {
94.       var path=new Stack<BSTNode>();
95.       if (_Root == null)
96.       {
97.         return null;
98.       }
99.       var active = _Root;
100.       while (true)
101.       {
102.         path.Push(active);
103.         if (active.Value == lookupvalue)
104.         {
105.           break;
106.         }
107.         if (active.Value > lookupvalue)
108.         {
109.           if (active.LeftNode == null)
110.             return active;
111.           active = active.LeftNode;
112.         }
113.         else // Must be <, no need to test
114.         {
115.           if (active.RightNode == null)
116.             return active;
117.           active = active.RightNode;
118.         }
119.       }
120.       var last = path.Pop();
121.       while(last.RightNode==null && path.Count > 0)
122.       {
123.         last = path.Pop();
124.       }
125.       return last.RightNode;
126.     }
127.     /// <summary>
128.     /// Find the node where a node would be inserted
129.     /// Not a red-black (balanced tree) implementation
130.     /// </summary>
131.     /// <param name="lookupvalue"></param>
132.     /// <returns></returns>
133.     public BSTNode ParentFind(int lookupvalue)
134.     {
135.       if (_Root == null)
136.       {
137.         return null;
138.       }
139.       var active = _Root;
140.       while (active != null)
141.       {
142.         if (active.Value == lookupvalue)
143.         {
144.           throw new DataException("Node with this value already exists");
145.         }
146.         if (active.Value > lookupvalue)
147.         {
148.           if(active.LeftNode==null)
149.             return active;
150.           active = active.LeftNode;
151.         }
152.         else // Must be <, no need to test
153.         {
154.           if (active.RightNode == null)
155.             return active;          
156.           active = active.RightNode;
157.         }
158.       }
159.       return active;
160.     }
161.   }
162. }