Binary Search Tree Visualizer
A Binary Search Tree is a hierarchical data structure that stores elements in a way that enables efficient searching, insertion, and deletion operations.
Each node in a BST has a value and at most two children: a left child and a right child.
The Binary Search Tree property dictates that the values in the left subtree of a node are less than or equal to the value of the node, while the values in the right subtree are greater.
Node: Each element in the BST is represented by a node containing a value and pointers to left and right children.
Root: The topmost node in the tree.
Parent and Children: Nodes have a parent node above them and children nodes below them.
Left Child and Right Child: Children are categorized based on their relation to their parent's value.
Subtree: A node and its descendants form a subtree.
Insertion: To insert a new element, compare its value with nodes as you traverse the tree. Move left for smaller values and right for larger values until you find an empty spot to insert the new node.
Search: Compare the target value with nodes while traversing the tree. This guides you to the correct subtree, narrowing the search space until you find the element or determine its absence.
Deletion: Deleting a node requires reorganizing the tree while maintaining the BST property. Different cases arise based on the node's children.
In-order Traversal: Traverse the left subtree, visit the current node, then traverse the right subtree. Produces values in ascending order.
Pre-order Traversal: Visit the current node, traverse the left subtree, then traverse the right subtree. Used for making a copy of the tree.
Post-order Traversal: Traverse the left subtree, traverse the right subtree, then visit the current node. Used for deleting nodes from the tree.
BSTs offer efficient average-case performance for search, insertion, and deletion when balanced.
Average time complexity for these operations is O(log n), where n is the number of nodes in the tree.
However, in the worst case, if the tree becomes skewed, operations can take O(n) time.
To ensure efficient operations in all cases, various balanced BSTs like AVL trees and Red-Black trees are used.
These trees maintain balance through rotations and color-based techniques, keeping the height logarithmic and preserving the O(log n) time complexity.
Binary Search Trees are used in databases, as their search efficiency aclass="slide" ids in quick retrieval of data.
They're also useful for implementing sorting algorithms like Binary Tree Sort.
In compilers, symbol tables are often implemented using BSTs.
Binary Search Trees are a powerful tool for efficient data storage, search, and manipulation.
Understanding their structure and properties is crucial for designing effective algorithms and data structures in computer science.
Javascript Implementation:
1 | class Node {
2 | constructor(value) {
3 | this.value = value;
4 | this.left = null;
5 | this.right = null;
6 | }
7 | }
8 |
9 | class BinaryTree {
10 | constructor() {
11 | this.root = null;
12 | }
13 |
14 | insert(value) {
15 | const newNode = new Node(value);
16 | if (!this.root) {
17 | this.root = newNode;
18 | return;
19 | }
20 |
21 | this._insertRecursive(this.root, newNode);
22 | }
23 |
24 | _insertRecursive(currentNode, newNode) {
25 | if (newNode.value < currentNode.value) {
26 | if (!currentNode.left) {
27 | currentNode.left = newNode;
28 | } else {
29 | this._insertRecursive(currentNode.left, newNode);
30 | }
31 | } else {
32 | if (!currentNode.right) {
33 | currentNode.right = newNode;
34 | } else {
35 | this._insertRecursive(currentNode.right, newNode);
36 | }
37 | }
38 | }
39 |
40 | search(value) {
41 | return this._searchRecursive(this.root, value);
42 | }
43 |
44 | _searchRecursive(currentNode, value) {
45 | if (!currentNode) {
46 | return false;
47 | }
48 |
49 | if (currentNode.value === value) {
50 | return true;
51 | } else if (value < currentNode.value) {
52 | return this._searchRecursive(currentNode.left, value);
53 | } else {
54 | return this._searchRecursive(currentNode.right, value);
55 | }
56 | }
57 |
58 | remove(value) {
59 | this.root = this._removeRecursive(this.root, value);
60 | }
61 |
62 | _removeRecursive(currentNode, value) {
63 | if (!currentNode) {
64 | return null;
65 | }
66 |
67 | if (value === currentNode.value) {
68 | if (!currentNode.left) {
69 | return currentNode.right;
70 | } else if (!currentNode.right) {
71 | return currentNode.left;
72 | } else {
73 | const minValue = this._findMinValue(currentNode.right);
74 | currentNode.value = minValue;
75 | currentNode.right = this._removeRecursive(currentNode.right, minValue);
76 | }
77 | } else if (value < currentNode.value) {
78 | currentNode.left = this._removeRecursive(currentNode.left, value);
79 | } else {
80 | currentNode.right = this._removeRecursive(currentNode.right, value);
81 | }
82 |
83 | return currentNode;
84 | }
85 |
86 | _findMinValue(node) {
87 | while (node.left) {
88 | node = node.left;
89 | }
90 | return node.value;
91 | }
92 | }
Python Implementation:
1 | class Node:
2 | def __init__(self, value):
3 | self.value = value
4 | self.left = None
5 | self.right = None
6 |
7 | class BinaryTree:
8 | def __init__(self):
9 | self.root = None
10 |
11 | def insert(self, value):
12 | new_node = Node(value)
13 | if not self.root:
14 | self.root = new_node
15 | return
16 |
17 | self._insert_recursive(self.root, new_node)
18 |
19 | def _insert_recursive(self, current_node, new_node):
20 | if new_node.value < current_node.value:
21 | if not current_node.left:
22 | current_node.left = new_node
23 | else:
24 | self._insert_recursive(current_node.left, new_node)
25 | else:
26 | if not current_node.right:
27 | current_node.right = new_node
28 | else:
29 | self._insert_recursive(current_node.right, new_node)
30 |
31 | def search(self, value):
32 | return self._search_recursive(self.root, value)
33 |
34 | def _search_recursive(self, current_node, value):
35 | if not current_node:
36 | return False
37 |
38 | if current_node.value == value:
39 | return True
40 | elif value < current_node.value:
41 | return self._search_recursive(current_node.left, value)
42 | else:
43 | return self._search_recursive(current_node.right, value)
44 |
45 | def remove(self, value):
46 | self.root = self._remove_recursive(self.root, value)
47 |
48 | def _remove_recursive(self, current_node, value):
49 | if not current_node:
50 | return None
51 |
52 | if value == current_node.value:
53 | if not current_node.left:
54 | return current_node.right
55 | elif not current_node.right:
56 | return current_node.left
57 | else:
58 | min_value = self._find_min_value(current_node.right)
59 | current_node.value = min_value
60 | current_node.right = self._remove_recursive(current_node.right, min_value)
61 | elif value < current_node.value:
62 | current_node.left = self._remove_recursive(current_node.left, value)
63 | else:
64 | current_node.right = self._remove_recursive(current_node.right, value)
65 |
66 | return current_node
67 |
68 | def _find_min_value(self, node):
69 | while node.left:
70 | node = node.left
71 | return node.value
Ruby Implementation:
1 | class Node
2 | attr_accessor :value, :left, :right
3 |
4 | def initialize(value)
5 | @value = value
6 | @left = nil
7 | @right = nil
8 | end
9 | end
10 |
11 | class BinaryTree
12 | attr_accessor :root
13 |
14 | def initialize
15 | @root = nil
16 | end
17 |
18 | def insert(value)
19 | new_node = Node.new(value)
20 | if @root.nil?
21 | @root = new_node
22 | return
23 | end
24 |
25 | insert_recursive(@root, new_node)
26 | end
27 |
28 | def insert_recursive(current_node, new_node)
29 | if new_node.value < current_node.value
30 | if current_node.left.nil?
31 | current_node.left = new_node
32 | else
33 | insert_recursive(current_node.left, new_node)
34 | end
35 | else
36 | if current_node.right.nil?
37 | current_node.right = new_node
38 | else
39 | insert_recursive(current_node.right, new_node)
40 | end
41 | end
42 | end
43 |
44 | def search(value)
45 | search_recursive(@root, value)
46 | end
47 |
48 | def search_recursive(current_node, value)
49 | return false if current_node.nil?
50 |
51 | if current_node.value == value
52 | return true
53 | elsif value < current_node.value
54 | search_recursive(current_node.left, value)
55 | else
56 | search_recursive(current_node.right, value)
57 | end
58 | end
59 |
60 | def remove(value)
61 | @root = remove_recursive(@root, value)
62 | end
63 |
64 | def remove_recursive(current_node, value)
65 | return nil if current_node.nil?
66 |
67 | if value == current_node.value
68 | if current_node.left.nil?
69 | return current_node.right
70 | elsif current_node.right.nil?
71 | return current_node.left
72 | else
73 | min_value = find_min_value(current_node.right)
74 | current_node.value = min_value
75 | current_node.right = remove_recursive(current_node.right, min_value)
76 | end
77 | elsif value < current_node.value
78 | current_node.left = remove_recursive(current_node.left, value)
79 | else
80 | current_node.right = remove_recursive(current_node.right, value)
81 | end
82 |
83 | current_node
84 | end
85 |
86 | def find_min_value(node)
87 | while node.left
88 | node = node.left
89 | end
90 | node.value
91 | end
92 | end
"Generate Random" -> generates a new binary search tree
"Insert Node" -> inserts a node with the given value
"Remove Node" -> removes a node with the given value
"Search" -> searches for a node with the given value
Learn more about binary search trees by clicking "Lessons" at the top of the page!
View the code implementation by clicking "Code" at the top of the page!