Как се определя времето за търсене на елемент в двоично дърво?

Времето за търсене на елемент в бинарно дърво зависи от неговата структура. Средно, за балансирано бинарно дърво, търсенето се извършва за O(log n), където n е броят на възлите, тъй като на всяка стъпка отхвърляме половината от останалите елементи. В най-лошия случай, ако дървото се превърне в списък (например, всички елементи са в една посока), времето за търсене става O(n).

Пример: ако дървото е балансирано, за да намерим елемент, го сравняваме с корена, след което отиваме в левия или десния поддърво, намалявайки броя на разглежданите възли наполовина на всяка стъпка.