# Binary Search Tree : Lowest Common Ancestor

# Binary Search Tree : Lowest Common Ancestor

+ 0 comments when I use root.data < v1 instead of v1 < root.data 2 test cases are failed, are there any difference to these? the position is just the difference right?

+ 0 comments **java 8 simplest solution**1. checking if both v1 & v2 less than current node then lca resides in left substree. 2. else if both v1 & v2 greater than current node then lca resides in right substree. 3. if not both previous then lca node is the node where v1 & v2 divide into different subtree or current node data is v1 or v2, so return this node.Node node = root; while(node != null){ if(v1 < node.data && v2 < node.data) node = node.left; else if(v1 > node.data && v2 > node.data) node = node.right; else return node; } return null; // if not found

+ 0 comments It's a binary tree, so you need to return the first node that is in between v1 and v2 (or where the value of the node equal v1 or v2).

Done recursively:

def lca(root, v1, v2): #Enter your code here if v1< root.info and v2<root.info: return lca(root.left, v1, v2) elif v1> root.info and v2>root.info: return lca(root.right, v1, v2) else: return root``

+ 0 comments The first picture provided in the challenge seems to have incorrect information. It shows 4 as the left child of 3 in the Binary Search Tree, but in reality, the left child of 3 should not be greater than 3.

+ 0 comments how is this considered as an easy problem ?

Sort 740 Discussions, By:

Please Login in order to post a comment