Binary Search Tree
DSA
Binary Tree
A Binary tree is a tree in which each node has at most two children. The two
children are usually called the left child and the right child.
A binary tree can be used to represent expressions, parse trees, and many
other types of data.
Binary trees are used in various applications and algorithms such as
searching, sorting, expression evaluation, and hierarchical data
representation. It provides an efficient way to organize and manipulate data.
Binary Tree
Binary Search Tree
A binary search tree is a binary tree in which the left subtree of a node
contains only nodes with values less than the node’s value, and the right
subtree contains only nodes with values greater than the node’s value.
This property makes binary search trees useful for searching and sorting.
The subtrees contains this property, thus are also binary search trees
themselves.
Binary Search Tree
BST Operations
BST operations:
• Delete
• Search
• Insert
• Traversal operations (Inorder, Preorder, Postorder)
BST offers efficient average-case time complexity for operations such as
search, insert, and delete operations with O(log n),
Applications of the BST
Key applications include:
• Symbol Tables and Databases
• Auto-complete and spell checking
• Binary Search
• File System Organization
• Dynamic sets and Ordered Data
• Range Queries and Interval Trees
• Priority Queues
• Optimization Algorithms
BST Implementation
A BST has a node that can have 2
maximum node children called left
and right, and a key variable that
contains the data or item. These
nodes will be the building block
used to chain other nodes together
and thus will create the BST.
BST Implementation
The class BST will have a Node root
set to null at the start, this will
contain the first data that will be
inserted.
BST Implementation
Inside class BinarySearchTree, insert
operation (method) is placed which
sets a node to the root if it still
contains the value null, if it has
value, it will check if the key value
if it is less than or greater than
through recursion and set the values
accordingly.
BST Implementation
Inside class BinarySearchTree, delete
method will delete a node, and then
adjust the position of the child node
to fill the gap of the deleted node
through recursion.
BST Implementation
Inside class BinarySearchTree, search
method will find the key in the BST
through recursion and will simply
return true if found or false if not
found.
BST Traversal
In BST, there are three ways to traverse:
• In-order traversal
• Preorder traversal
• Postorder traversal
Inorder Traversal
traversal refers to the process
of systematically visiting or
accessing each element in a data
structure, ensuring that every
element is accessed at least
once.
Inorder traversal first traverse
the left subtree, then visit the Inorder traversal will have an output:
root, then traverse the right 8 12 20 22 25 30 40
subtree Time complexity = O(N)
preorder Traversal
preorder traversal first visit
the root, then traverse left
subtree, then traverse the right
subtree.
preorder traversal will have an output:
22 12 8 20 30 25 40
Time Complexity: O(N)
postorder Traversal
preorder traversal first traverse
left subtree, then traverse the
right subtree, then visit the
root.
postorder traversal will have an output:
8 20 12 25 40 30 22
Time Complexity: O(N)
BST Implementation
Inside class BinarySearchTree,
inorder method will traverse the BST
using inorder traversal.
BST Implementation
Inside class BinarySearchTree,
preorder method will traverse the BST
using preorder traversal.
BST Implementation
Inside class BinarySearchTree,
postorder method will traverse the
BST using postorder traversal.
