"""

Distance between Nodes of BST
Problem Description

Given a binary search tree.
Return the distance between two nodes with given two keys B and C. It may be assumed that both keys exist in BST.

NOTE: Distance between two nodes is number of edges between them.



Problem Constraints
1 <= Number of nodes in binary tree <= 1000000

0 <= node values <= 10^9



Input Format
First argument is a root node of the binary tree, A.

Second argument is an integer B.

Third argument is an integer C.



Output Format
Return an integer denoting the distance between two nodes with given two keys B and C



Example Input
Input 1:

    
         5
       /   \
      2     8
     / \   / \
    1   4 6   11
 B = 2
 C = 11
Input 2:

    
         6
       /   \
      2     9
     / \   / \
    1   4 7   10
 B = 2
 C = 6


Example Output
Output 1:

 3
Output 2:

 1


Example Explanation
Explanation 1:

 Path between 2 and 11 is: 2 -> 5 -> 8 -> 11. Distance will be 3.
Explanation 2:

 Path between 2 and 6 is: 2 -> 6. Distance will be 1

"""

# Definition for a  binary tree node
# class TreeNode:
#    def __init__(self, x):
#        self.val = x
#        self.left = None
#        self.right = None

# Finding LCA for key1 and key2
def lca(root, key1, key2):
    if root == None:
        return

    if key1 < root.val and key2 < root.val:
        return lca(root.left, key1, key2)
        
    elif key1 > root.val and key2 > root.val:
        return lca(root.right, key1, key2)
        
    else:
        return root


# Finding distance of key from Root node
def find_distance(root, key, distance):
    if root == None:
        return 0
    
    distance += 1
    if key < root.val:
        return find_distance(root.left, key, distance)
    elif key > root.val:
        return find_distance(root.right, key, distance)
    else:
        return distance
    

class Solution:
    # @param A : root node of tree
    # @param B : integer
    # @param C : integer
    # @return an integer
    def solve(self, A, B, C):
        
        lca_node = lca(A, B, C)
        
        distance_lca_node = find_distance(A, lca_node.val, -1)
        distance_key1 = find_distance(A, B, -1)
        distance_key2 = find_distance(A, C, -1)
        
        return distance_key1 + distance_key2 - 2*distance_lca_node
        
        
        
