> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/trees/bst-node-distance.md).

# 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%)

```java
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) {
        // Write your code here
        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++) {
            addTreeNode(root, nums[i]);
        }
        return root;
    }

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

    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:
>
> 先建BST, 再找LCA，两个node的距离=dist(root, n1) + dist(root, n2) - 2\*dist(root, LCA). 用 findPathFromRoot来找到这三个距离。 dist = path.size() -1.

## Reference

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