TreesLesson 29Free preview

DSA Binary Search Trees

This lesson is part of DSA · All levels

Summary

A binary search tree is a binary tree in order: the value of each left node is smaller and the value of the right child is larger than the parent. This makes searching, inserting, and removing average because each step throws half a tree away. When the tree becomes skewed, its performance can decrease to O(n).

Key points

The left subtree value is smaller and the right subtree is larger than the parent
In-order traversal yields a sequence of values
Average operations are poor when unbalanced
The search uses the direction of the comparison to discard half the tree

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.