Зависит от типа дерева. Бинарное дерево поиска (BST): сравниваешь с корнем, идёшь влево (меньше) или вправо (больше) — O(log n) в среднем, O(n) в худшем. Сбалансированные деревья (AVL, красно-чёрное) гарантируют O(log n).
BFS (в ширину) — очередь, обходит уровень за уровнем. DFS (в глубину) — стек/рекурсия, три варианта: inorder (left-root-right, даёт отсортированный порядок в BST), preorder (root-left-right), postorder (left-right-root).
B-tree используется в БД — оптимизировано для дискового I/O, узлы содержат много ключей.