LintCode: BST Node Distance

BST Node Distance



Similar Problems:


Description

Given a list of numbers, construct a BST from it 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

Example

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

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/bst-node-distance
// Basic Ideas:
// Least Common Ancestor
// Complexity: Time O(n), Space O(n)
/**
 * @param numbers: the given list
 * @param node1: the given node1
 * @param node2: the given node2
 * @return: the distance between two nodes
 */
func getDistance(root *TreeNode, node *TreeNode) int {
    if node.Val == root.Val { return 0 }
    p := root.Left
    if root.Val < node.Val { p = root.Right }
    return 1 + getDistance(p, node)
}

func bstDistance (numbers []int, node1 int, node2 int) int {
    if node1 == node2 || len(numbers) <= 2 { return -1 }
    // TODO: how to combine below two lines as one?
    p1, p2 := &TreeNode{}, &TreeNode{}
    p1, p2 = nil, nil
    // Build BST
    root := &TreeNode{}
    for i, val := range numbers {
        q := &TreeNode{nil, nil, val}
        if val == node1 { p1 = q }
        if val == node2 { p2 = q }
        if i == 0 {
            root = q
            continue
        }

        p := root
        for true {
            if q.Val < p.Val {
                if p.Left == nil {
                    p.Left = q
                    break
                }
                p = p.Left
            } else {
                if p.Right == nil {
                    p.Right = q
                    break
                }
                p = p.Right
            }
        }
    }

    // Invalid input
    if p1 == nil || p2 == nil { return -1 }
    min, max := 0, 0
    if node1 > node2 {
        max, min = node1, node2
    } else {
        max, min = node2, node1
    }

    // find distance
    p := root
    for p != nil {
        if p.Val > max {
            p = p.Left
            continue
        }
        if p.Val < min {
            p = p.Right
            continue
        }
        return getDistance(p, p1) + getDistance(p, p2)
    }
    return -1
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.