Find the 1st common ancestor of two nodes in a binary tree

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

My initial thoughts:
Consider two nodes u and v, together with a root node. There are several cases we need to consider:

  1. u is the ancestor of v. then return u.
  2. v is the ancestor of u. then return v.
  3. left subtree of root contains u and right subtree of root contains v. then return root.
  4. left subtree of root contains v and right subtree of root contains u. then return root.

My initial codes:

	public static BinaryTreeNode<Integer> FCA(BinaryTreeNode<Integer> root,
			BinaryTreeNode<Integer> u, BinaryTreeNode<Integer> v) {
		boolean uInLeft = contain(root.getLeft(), u);
		boolean uInRight = contain(root.getRight(), u);
		boolean vInLeft = contain(root.getLeft(), v);
		boolean vInRight = contain(root.getRight(), v);

		if (!uInLeft && !uInRight && !vInLeft && !vInRight)
			return null;

		if (uInLeft && vInRight)
			return root;
		else if (vInLeft && uInRight)
			return root;
		else if (root == u && (vInLeft || vInRight))
			return root;
		else if (root == v && (uInLeft || uInRight))
			return root;
		else {
			BinaryTreeNode<Integer> leftAncestor = FCA(root.getLeft(), u, v);
			BinaryTreeNode<Integer> rightAncestor = FCA(root.getRight(), u, v);
			if (leftAncestor == null && rightAncestor != null)
				return rightAncestor;
			else if (leftAncestor != null && rightAncestor == null)
				return leftAncestor;
			else
				return null;
		}

	}

	public static boolean contain(BinaryTreeNode<Integer> root,
			BinaryTreeNode<Integer> node) {
		if (root == node)
			return true;
		else if (root == null)
			return false;
		else
			return contain(root.getLeft(), node)
					|| contain(root.getRight(), node);
	}

Solution:

	public static BinaryTreeNode<Integer> commonAncestor(
			BinaryTreeNode<Integer> root, BinaryTreeNode<Integer> u,
			BinaryTreeNode<Integer> v) {
		if (contain(root.getLeft(), u) && contain(root.getLeft(), v))
			return commonAncestor(root.getLeft(), u, v);
		if (contain(root.getRight(), u) && contain(root.getRight(), v))
			return commonAncestor(root.getRight(), u, v);
		return root;
	}

Comments: The solution simplifies mine by combing cases.There are actually two simple cases: u and v are along the same side v.s. u and v are on different sides.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: