# BST Node Distance

Binary Search Tree

Medium

### Description

Given a list of numbers, construct a BST from it(you need to insert nodes one-by-one with the given order to get the BST) and find the distance between two given nodes.

If two nodes do not appear in the BST, return -1
We guarantee that there are no duplicate nodes in BST
The node distance means the number of edges between two nodes

### Example

input:
numbers = [2,1,3]
node1 = 1
node2 = 3
output:
2

## Analysis

### 思路：

@giesekus0903

# 构建BST
# 求LCA
# 计算LCA 到两点间的距离并相加，返回

# build balance BST
# find lca of node1 and node2
# dist(node1,lca) + dist(node2,lca)

(LintCode: Total runtime 419 ms; beats 86.80%)

public class Solution {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode (int v) {
val = v;
}
}
/**
* @param numbers: the given list
* @param node1: the given node1
* @param node2: the given node2
* @return: the distance between two nodes
*/
public int bstDistance(int[] numbers, int node1, int node2) {
TreeNode root = buildBST(numbers);
TreeNode lca = LCA(root, node1, node2);
int dist1 = dist(lca, node1);
int dist2 = dist(lca, node2);
if (dist1 < 0 || dist2 < 0) {
return -1;
}
return  dist1 + dist2;
}

private TreeNode buildBST(int[] nums) {
TreeNode root = new TreeNode(nums[0]);
for (int i = 1; i < nums.length; i++) {
}
return root;
}

private void addTreeNode(TreeNode root, int val) {
if (val < root.val) {
if (root.left == null) {
root.left = new TreeNode(val);
} else {
}
} else {
if (root.right == null) {
root.right = new TreeNode(val);
} else {
}
}
}

private TreeNode LCA(TreeNode root, int n1, int n2) {
/*
if (n1 > n2) {
return LCA(root, n2, n1);
}
if (n1 <= root.val && root.val <= n2) {
return root;
}
if (n2 <= root.val) {
return LCA(root.left, n1, n2);
} else {
return LCA(root.right, n1, n2);
}
*/
if (root == null) {
return null;
}
if (n1 > root.val && n2 > root.val) {
return LCA(root.right, n1, n2);
} else if (n1 < root.val && n2 < root.val) {
return LCA(root.left, n1, n2);
} else {
return root;
}
}

// find depth from root to node
private int dist(TreeNode root, int v) {
if (root == null) {
return -1;
}

if (root.val == v) {
return 0;
}
if (root.val > v) {
int left = dist(root.left, v);
if (left < 0) {
return -1;
}
return left + 1;
} else {
int right = dist(root.right, v);
if (right < 0) {
return -1;
}
return right + 1;
}
}

}

@yuhzeng:

## Reference

https://www.geeksforgeeks.org/shortest-distance-between-two-nodes-in-bst/