# 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/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trees/bst-node-distance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.