# If the tree is not binary search tree (BST), How to do ?

• Yes, when looking at this problem, I was careless and didn't notice the tree is binary search tree. And I also solve this problem, so I want to share with you.

The following is my ideas and code :
traversal the tree

• `1) if find two p and q, return 2`
• `2) if find one of p and q, return 1 and then rollback to the parent node, the common node also rollback to the parent node`
• `3) if find nothing of p or q, return 0 and do nothing to common node.`
``````private TreeNode common = null;

/**
*
* 27 / 27 test cases passed.
* Status: Accepted
* Runtime: 9 - 10ms, bit 26.45% - 14.05%
*
* @param root
* @param p
* @param q
* @return
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
helper(root, p, q);
return common;
}

/**
* @param root
* @param p
* @param q
* @return
*/
private int helper(TreeNode root, TreeNode p, TreeNode q) {
int count = 0;
if (root == null) return count;
if (root.val == p.val || root.val == q.val) {
if (common == null) {
common = root;
count = 1;
} else return 2;
}
int res = helper(root.left, p, q);
if (res == 1) common = root;
else if (res == 2) return res;

return count + res + helper(root.right, p, q);
}
``````

• I did the same mistake. This is my stupid passed solution.

``````27 / 27 test cases passed.
Status: Accepted
Runtime: 9 ms
Your runtime beats 26.49% of java submissions.

public class Q235LowestCommonAncestorofaBinarySearchTree {
TreeNode commonAncestor = null;
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
//if this is null, means end of tree
if(root == null) return null;
TreeNode leftResult = lowestCommonAncestor2(root.left, p, q);
TreeNode rightResult = lowestCommonAncestor2(root.right, p, q);
//before every check, first check if the commonAncestor has found
if(commonAncestor != null) return commonAncestor;

//two nodes come to one common ancestor
//if the left leave and right leave are not null, this node is the first common ancestor
if((leftResult != null) && (rightResult != null)){
commonAncestor = root;
return root;
}
//if one of the leafs is not null
else if(leftResult != null || (rightResult != null)){
//check current root, if it is one of two nodes, this is the first common ancestor
if((root.val == p.val) || (root.val == q.val)){
commonAncestor = root;
}
//if the current root is not the one, return the one that is not null to parent
return leftResult != null ? leftResult : rightResult ;
}
else {
//if both leafs are null, check current root
//if it belongs to the two nodes, return this root
if((root.val == p.val) || (root.val == q.val)){
return root;
}
//or no result in this subtree, return null
return null;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.