Distances in Binary Search Trees

Given an array representing values to be added to an empty binary search tree in order, and a pair of these values, return the shortest path distance between these values in the tree after all values have been inserted.

Note 1: the array contains distinct numbers

Note 2: The values in the array is added to the binary search tree as leaves one by one in order. You can reference or directly use this template C++ code for reading input and building the binary tree. Template at the end

Input format:
line 1: [node values for input tree]
line 2: [node1] [node2]

Examples

Input:
3 1 5 7 2 4
1 7
Output:
3

The shortest path from 1 to 7 is through their common ancestor 3. The BST is constructed as:

      3
     / \
    /   \
   1     5
    \   / \
     2 4   7

Input:
3 1 5 7 2 4
3 4
Output:
2

This is because in the completed tree, 5 is a child of 3, and 4 is a child of 5.

Starter code:

#include <stdio.h>
#include <vector>
#include <iostream>
#include <sstream>
#include <cassert>

struct Node {
    Node* left; 
    Node* right;
    int   val; 
};

// insert the val into leaves of the tree rooted at `root`
// if root is nil, allocate a node for val
// returns the root of the tree (new tree if root==null)
Node* insert(Node* root, int val) {
    if (root == NULL) {
    	Node* node = new Node;
    	node->left = NULL;
    	node->right = NULL;
    	node->val = val;
    	return node;
    }

    if (val < root->val)
	    root->left = insert(root->left, val); 
    else
	    root->right = insert(root->right, val);

    return root;
}

// debug utility
void print(Node* root, int indent) {
    if (root == NULL) return;
    print(root->right, indent+4);
    for (int i=0; i<indent; i++) printf(" ");
    printf("%d\n", root->val);
    print(root->left, indent+4);
}


int main() {
    std::vector<int> A;
    int a;
    std::string line;
    std::getline(std::cin, line);
    std::stringstream ss(line);
    while (ss >> a) {
	    A.push_back(a); 
    }
    int n1, n2; 
    std::cin >> n1 >> n2;

    Node* root = NULL;
    for (int i=0; i<A.size(); i++) {
	    root = insert(root, A[i]); 
    }

    // print(root,0);

    // TODO: Implement your dist function and output its result to stdout
    //std::cout << dist(root, n1, n2) << "\n";
}