Binary search trees (BST)

Binary search tree (16:05)

Now that we鈥檙e getting into more complex data structures, having more complex operations, it鈥檚 helpful to have a tool for visualization. Here鈥檚 a tool developed by David Galles, formerly of University of San Francisco, now a staff engineer at Google. Try inserting a few nodes with numeric values, then try searching and deleting. See if you can create examples of case 4 for deletion, where the left child of the target node has a right child.

Resources

• BST.pdf

Comprehension check

1. True or false? A binary search tree is a rooted tree.
2. True or false? A node in a binary tree may have three or more children.
3. Given an interior node in the tree, the node鈥檚 left subtree contains only values _____ than that of the node.
4. Average case complexity for insertion, finding, and deletion in a binary search tree is O(________).

Answers: u 苾ol / ss菨l / 菨sl蓯蔁 / 菨n晒蕠

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.