import java.lang.*;
import java.util.*;
import node.*;

class LowestCommonAncestor {
	public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null)
			return null;
		else if (p.val < root.val && q.val < root.val)
			return lowestCommonAncestor(root.left, p, q);
		else if (p.val > root.val && q.val > root.val)
			return lowestCommonAncestor(root.right, p, q);
		return root;
	}

	public static void main(String[] args) {
		TreeNode leftLeaf = new TreeNode(0);
		TreeNode lMiddleLeaf = new TreeNode(3);
		TreeNode rMiddleLeaf = new TreeNode(5);
		TreeNode lRightLeaf = new TreeNode(7);
		TreeNode rRightLeaf = new TreeNode(9);
		TreeNode lowerLeftParent = new TreeNode(4, lMiddleLeaf, rMiddleLeaf);
		TreeNode leftParent = new TreeNode(2, leftLeaf, lowerLeftParent);
		TreeNode rightParent = new TreeNode(8, lRightLeaf, rRightLeaf);
		TreeNode root = new TreeNode(6, leftParent, rightParent);
		System.out.println(lowestCommonAncestor(root, leftLeaf, lowerLeftParent).val);
	}
}