Python DSALesson 100Free preview

Binary Search Trees

This lesson is part of Python · All levels

Summary

This lesson discusses Binary Search Tree (BST), a variation of binary tree that has strict value sequence rules. The value on the left subtree is always smaller and the value on the right subtree is always larger than its parent. This rule makes searching, inserting, and deleting data run average as long as the tree remains balanced.

Key points

BST rule: left < root < right, and is recursive for each subtree.
Searching on BST throws out half a subtree at each step so it's like binary search.
If the data is entered in orderly order, the BST deviates to a linked list and its operation becomes O(n).
The main operation of BST is to insert, search, and delete with each maintaining the order rule.
Duplicate nodes are generally ignored or kept in the calculation depending on the implementation policy.

Full lesson

Code examples and quizzes

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