armorrison
BAN USER+1 Nice. Very minimal solution. This assumes data is an identifier, which I wasn't assuming, but should have. I like the return counter... slick!
- armorrison November 08, 2012Not sure if I am breaking rules of the asker with this solution. (I added params to track the parent as you look for the child)
class Program
{
static void Main(string[] args)
{
Node node5 = new Node(5, null, null);
Node node4 = new Node(4, null, null);
Node node3 = new Node(3, null, null);
Node node2 = new Node(2, node4, node5);
Node node1 = new Node(1, node2, node3);
Node common = NodeHelper.ParentFinder(node1, node4, node3);
Console.WriteLine(common.data);
Console.ReadLine();
}
}
class Node{
public int data;
public Node leftchild;
public Node rightchild;
public Node(int _data, Node _leftchild, Node _rightchild)
{
data = _data;
leftchild = _leftchild;
rightchild = _rightchild;
}
//adding some helper fields
public Node parent;
public int level;
}
static class NodeHelper
{
public static Node ParentFinder(Node root, Node node1, Node node2)
{
if (nodeParentPopulater(root, null, node1, 0) && nodeParentPopulater(root, null, node2, 0))
{
//continue
}
else
{
//nodes not found
return null;
}
Node temp1 = node1;
Node temp2 = node2;
//find each nodes parent node that lives at the same level
while (temp1.level > temp2.level)
{
temp1 = temp1.parent;
}
while (temp1.level < temp2.level)
{
temp2 = temp2.parent;
}
//now start checking if the nodes are the same
while (!temp1.Equals(temp2))
{
temp1 = temp1.parent;
temp2 = temp2.parent;
}
//parents are the same. return the parent node
return temp1;
}
private static bool nodeParentPopulater(Node node, Node parentNode, Node nodeToFind, int level)
{
bool found = false;
node.parent = parentNode;
node.level = level;
if (node.Equals(nodeToFind)) return true;
if (node.leftchild != null)
{
found = nodeParentPopulater(node.leftchild, node, nodeToFind, level + 1);
}
if (!found && node.rightchild != null)
{
found = nodeParentPopulater(node.rightchild, node, nodeToFind, level + 1);
}
return found;
}
}
It functions for non-unique values, it just uses the nodes closest to the root.
- armorrison November 08, 2012