Binary Search Trees
A Binary Search Tree is a Binary Tree with the Binary Search constraint applied. For every Node n, the value of the left child is less than the value of n and the value of the right child is greater than the value of n.
This gives a Binary Search Tree a total-order that a Binary Tree does not have. This ordering enables faster searches, compared to a Binary Tree. Search speed in a BST depends on the depth of the Node we're searching for.
Time complexity for search in a balanced Binary Search Tree is O(log(n)). Time complexity to traverse the whole Tree though is still O(n).
The number of comparisons needed to find a Node is determined by the depth of the Node. In the worst-case, the Node is a leaf-Node with depth equal to the depth of the Tree itself. Regardless of whether or not the Tree is balanced, the depth of the Tree is the primary factor in the time to find a Node.
In the worst-case, a Binary Search Tree is simply a Linked List. This would occur when a Binary Search Tree is constructed by inserting a List of values in sorted order. In this case, the runtime to find a given Node would degrade to O(n).