How is the efficiency of search in an unbalanced data tree determined?

The efficiency of search in an unbalanced tree is determined by the depth of the node where the desired element is located. In the worst case, if the tree degenerates into a list, the search time becomes linear — O(n). On average, efficiency depends on the structure of the tree and data distribution. To estimate it, the height of the tree is usually used: the taller the tree, the longer the search. In Go, search in a binary tree can be implemented as follows:

func search(node *Node, key int) *Node {
    if node == nil || node.key == key {
        return node
    }
    if key < node.key {
        return search(node.left, key)
    }
    return search(node.right, key)
}

If the tree is unbalanced, the depth can be large, which reduces efficiency.