Get startedGet started for free

Binary Search Tree (BST)

1. Binary Search Tree (BST)

Let's explore binary search trees, which are a special kind of binary tree.

2. Definition

Recall that a binary tree is a tree where each node has zero, one, or two children. In a binary search tree, the left subtree of a node contains only nodes with values less than the node itself, whereas the right subtree contains nodes with values greater than the node. The left and right subtrees must also be binary search trees.

3. Implementation

To work with binary search trees, we will use the familiar TreeNode class. The BinarySearchTree class will implement the main operations and provide the root node's value.

4. Searching

Suppose are searching for the value 72.

5. Searching

We begin by comparing the root node with the search number. As 72 is greater than 60,

6. Searching

we continue searching in the right subtree and compare the first node of this subtree, 70, with 72. As 72 is greater,

7. Searching

we continue searching in the right subtree. 72 is less than 75,

8. Searching

so we continue with the left tree.

9. Searching

In this example, we do find the number.

10. Searching

To implement this operation, we set current_node as the root. As long as we have nodes to visit, we check if search_value is equal to current_node's data. If yes, we return True. If it is less, current_node becomes current_node's left child. Otherwise, current_node becomes current_node's right child. If the loop ends without finding the search_value, we return False.

11. Inserting

Let's implement the insert operation. We first create a new_node with the data. If the tree doesn't have a root node,

12. Inserting

the root is the new_node, and the execution finishes.

13. Inserting

If the tree has a root,

14. Inserting

current_node is the root. We iterate until we insert the new_node. We check if the data to insert is less than current_node's data. If yes, we check if current_node has a left node. If it doesn't,

15. Inserting

new_node becomes the current_node's left_child, and execution finishes.

16. Inserting

However, if current_node has a left_child,

17. Inserting

we set current_node as the left_child. We iterate until we find the place for the new_node.

18. Inserting

Let's look at inserting a value greater than current_node's data. If current_node doesn't have a right_child,

19. Inserting

new_node becomes the right_child, and the execution finishes.

20. Inserting

But if current_node has a right_child,

21. Inserting

current_node is set as the right_child and iteration continues. Let's finish by comparing new_node with current_node. As 68 is less than 70 and current_node doesn't have a left_child,

22. Inserting

the new_node will become the left_child.

23. Deleting

We'll now have a look at the delete operation. If the node we want to delete has no children,

24. Deleting

we delete it.

25. Deleting

If the node has one child,

26. Deleting

we delete the node and connect the child with

27. Deleting

the node's parent.

28. Deleting

If the node being deleted has two children, we

29. Deleting

replace it with its successor. The successor is the node with the smallest value greater than the value of the node we want to delete. To find the successor,

30. Deleting

visit the right child of the node being deleted,

31. Deleting

and keep visiting its left nodes

32. Deleting

until the end.

33. Deleting

Then, we replace

34. Deleting

the node with its successor.

35. Deleting

If the successor has a right child,

36. Deleting

this child becomes the left child of the successor's parent.

37. Uses

BSTs can be used to order lists efficiently. When adding or removing elements, there is no need to re-order all of them again. BSTs are faster at searching than arrays and linked lists and faster at inserting and deleting than arrays. They are also used to implement more advanced data structures like dynamic sets, lookup tables, and priority queues.

38. Let's practice!

Let's practice!

Create Your Free Account

or

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.