1: public class Trees
2: {
3: // This is the public kick-off method, orders the first/second
4: public Node<int> FindLowestCommonAncestor(int first, int second, Node<int> root)
5: {
6: // if first and second happen to be same, it's simply a find
7: if (first == second)
8: {
9: return Find(first, root);
10: }
11:
12: // otherwise, order the first and second by value
13: return first < second
14: ? FindLowestCommonAncestorTraversal(first, second, root)
15: : FindLowestCommonAncestorTraversal(second, first, root);
16: }
17:
18: // a helper method that simply finds a node in the BST
19: public Node<int> Find(int value, Node<int> current)
20: {
21: if (current != null)
22: {
23: if (current.Value == value)
24: {
25: return current;
26: }
27:
28: return value < current.Value
29: ? Find(value, current.Left)
30: : Find(value, current.Right);
31: }
32:
33: return null;
34: }
35:
36: // the actual traversal
37: private Node<int> FindLowestCommonAncestorTraversal(int smaller, int larger, Node<int> current)
38: {
39: if (current != null)
40: {
41: // if larger < value then smaller is also by definition, both left
42: if (larger < current.Value)
43: {
44: return FindLowestCommonAncestorTraversal(smaller, larger, current.Left);
45: }
46:
47: // if smaller is > value, then larger is also by definition, both right
48: if (smaller > current.Value)
49: {
50: return FindLowestCommonAncestorTraversal(smaller, larger, current.Right);
51: }
52:
53: // otherwise, we found divergent point, make sure nodes actually exist
54: if (Find(smaller, current) != null && Find(larger, current) != null)
55: {
56: return current;
57: }
58: }
59:
60: return null;
61: }
62: }