Find the lowest common ancestor in the binary search tree

Question

I have the following code to find the lowest common ancestor (the lowest node, which has both a and b as descendants):

public static Node LCA(Node root, Node a, Node b) { if (root == null) return null; if (root.IData == a.IData || root.IData == b.IData) return root; if (root.RightChild != null && (root.RightChild.IData == a.IData || root.RightChild.IData == b.IData)) return root; if (root.LeftChild != null && (root.LeftChild.IData == a.IData || root.LeftChild.IData == b.IData)) return root; if (root.IData > a.IData && root.IData > b.IData) return LCA(root.LeftChild, a, b); else if (root.IData < a.IData && root.IData < b.IData) return LCA(root.RightChild, a, b); else return root; } 

Binary search tree

  20 / \ 8 22 / \ 4 12 / \ 10 14 

Question

It does not work in the following cases:

LCA (4, 8) = 20, but should be 8.

LCA (8, 12) = 20, but should be 8

LCA (8, 23) = 20, non-existent number (23) as a parameter.

Any thoughts?

Where node is

 class Node { public int IData {get; set;} public Node RightChild {get; set;} public Node LeftChild {get; set;} } 

Answer 1

If the IData of root is different from both a and b 's, but one of the root has the same IData as one of the two, you return root , but by your definition you should return the child if both nodes are in the same subtree . Since you also want to check that both nodes are actually in the tree, this check must be performed before any return.

 public static Node LCA(Node root, Node a, Node b) { if (root == null) return null; // what if a == null or b == null ? Node small, large, current = root; if (a.IData < b.IData) { small = a; large = b; } else { small = b; large = a; } if (large.IData < current.IData) { do { current = current.LeftChild; }while(current != null && large.IData < current.IData); if (current == null) return null; if (current.IData < small.IData) return LCA(current,small,large); // if we get here, current has the same IData as one of the two, the two are // in different subtrees, or not both are in the tree if (contains(current,small) && contains(current,large)) return current; // at least one isn't in the tree, return null return null; } else if (current.IData < small.IData) { // the symmetric case, too lazy to type it out } else // Not both in the same subtree { if (contains(current,small) && contains(current,large)) return current; } return null; // at least one not in tree } public static bool contains(Node root, Node target) { if (root == null) return false; if (root.IData == target.IData) return true; if (root.IData < target.IData) return contains(root.RightChild,target); return contains(root.LeftChild,target); } 

Answer 2

Is IData (==) defined? If not, you are simply comparing the links, not the objects themselves.

This explains it pretty well: http://www.ikriv.com/en/prog/info/dotnet/ObjectEquality.html

Answer 3

Here is the C # version:

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace LCA { class Node { public Node(int data, Node a, Node b) { IData = data; LeftChild = a; RightChild = b; } public int IData { get; set; } public Node RightChild { get; set; } public Node LeftChild { get; set; } } class Program { static Node a = new Node(10, null, null); static Node b = new Node(14, null, null); static Node ab = new Node(12, a, b); static Node c = new Node(4, null, null); static Node ac = new Node(8, c, ab); static Node d = new Node(22, null, null); static Node root = new Node(20, ac, d); static void Main(string[] args) { string line; line = Console.ReadLine(); string[] ip = line.Split(' '); int ip1 = -1; int ip2 = -1; if (ip.Length == 2) { Int32.TryParse(ip[0], out ip1); Int32.TryParse(ip[1], out ip2); int i = -1; Node node = null; Node node1 = new Node(ip1, null, null); Node node2 = new Node(ip2, null, null); if (contains(root, node1)) { if (!contains(root, node2)) node = node1; } else { if (!contains(root, node2)) node = new Node(-1, null, null); else node = node2; } if (node == null) node = LCA(root, node1, node2); Int32.TryParse(node.IData.ToString(), out i); Console.WriteLine(i); Console.ReadLine(); } } public static Node LCA(Node root, Node a, Node b) { if (root == null) return null; Node small, large, current = root; if (a.IData < b.IData) { small = a; large = b; } else { small = b; large = a; } if (large.IData < current.IData) { do { current = current.LeftChild; } while (current != null && large.IData < current.IData); if (current == null) return null; if (current.IData < small.IData) return LCA(current, small, large); // if we get here, current has the same IData as one of the two, the two are // in different subtrees, or not both are in the tree if (contains(current, small) && contains(current, large)) return current; // at least one isn't in the tree, return null return null; } else if (current.IData < small.IData) { do { current = current.RightChild; } while (current != null && current.IData < small.IData); if (current == null) return null; if (current.IData < small.IData) return LCA(current, small, large); // if we get here, current has the same IData as one of the two, the two are // in different subtrees, or not both are in the tree if (contains(current, small) && contains(current, large)) return current; // at least one isn't in the tree, return null return null; } else // Not both in the same subtree { if (contains(current, small) && contains(current, large)) return current; } return null; // at least one not in tree } public static bool contains(Node root, Node target) { if (root == null) return false; if (root.IData == target.IData) return true; if (root.IData < target.IData) return contains(root.RightChild, target); return contains(root.LeftChild, target); } } } 

Answer 4

Here you go:

 Console.WriteLine("\n\n /* Lowest Common Ancestor */"); int v1 = 4, v2 = 8; Node lca = LCA(Root, v1, v2); Console.WriteLine("LCA of {0} and {1} is: {2}", v1, v2, (lca != null ? lca.Data.ToString() : "No LCA Found")); public static Node LCA(Node root, int v1, int v2) { if (root == null) return null; if (root.Data > v1 && root.Data > v2) return LCA(root.Left, v1, v2); else if (root.Data < v1 && root.Data < v2) return LCA(root.Right, v1, v2); else return root; } 

Answer 5

Just add an iterative version of C # to search for a common ancestor in the Binary Search tree for reference:

 public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2) { //ensure both elements are there in the bst var n1 = this.BstFind(e1, throwIfNotFound: true); if(e1 == e2) { return n1; } this.BstFind(e2, throwIfNotFound: true); BinaryTreeNode leastCommonAcncestor = this._root; var iterativeNode = this._root; while(iterativeNode != null) { if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2)) { iterativeNode = iterativeNode.Left; } else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2)) { iterativeNode = iterativeNode.Right; } else { //ie; either iterative node is equal to e1 or e2 or in between e1 and e2 return iterativeNode; } } 

Where to Find is defined below

 public BinaryTreeNode Find(int e, bool throwIfNotFound) { var iterativenode = this._root; while(iterativenode != null) { if(iterativenode.Element == e) { return iterativenode; } if(e < iterativenode.Element) { iterativenode = iterativenode.Left; } if(e > iterativenode.Element) { iterativenode = iterativenode.Right; } } if(throwIfNotFound) { throw new Exception(string.Format("Given element {0} is not found", e); } return null; } 

And BinaryTreeNode is defined as:

 class BinaryTreeNode { public int Element; public BinaryTreeNode Left; public BinaryTreeNode Right; } 

** tests **

 [TestMethod] public void LeastCommonAncestorTests() { int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 }; int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22}; BinarySearchTree bst = new BinarySearchTree(); foreach (int e in a) { bst.Add(e); bst.Delete(e); bst.Add(e); } for(int i = 0; i < b.Length; i++) { var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]); Assert.IsTrue(n.Element == b[i]); } } 

Answer 6

 public static Node LCA(Node root, Node a, Node b) { if (root == null) return null; if (root.IData > a.IData && root.IData > b.IData) return LCA(root.LeftChild, a, b); if (root.IData < a.IData && root.IData < b.IData) return LCA(root.RightChild, a, b); return root; }