Scribd
Upload
17 views

Binary Tree Sort Algorithm

Binary Tree Sort is a sorting algorithm that leverages a binary search tree

Uploaded by

Resonous Com
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views

Binary Tree Sort Algorithm

Binary Tree Sort is a sorting algorithm that leverages a binary search tree

Uploaded by

Resonous Com
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Binary Tree Sort is a sorting algorithm that leverages a binary search tree (BST) to sort elements.

The basic idea is to insert each element of the input list into a BST, then perform an in-order
traversal of the tree to retrieve the elements in sorted order.

Here’s a step-by-step algorithm for Binary Tree Sort:

Algorithm: Binary Tree Sort

Input:

A list or array of elements

L.

Output:

A sorted list or array

L
sorted
Lsorted .

Steps:

1 Define a Tree Node: Create a class for the nodes of the binary search tree (BST). Each node
should store:

◦ The value of the node.


◦ References to the left and right children.
2 Insert Function: Write a function to insert a new value into the BST. This function will:

◦ Start at the root.


◦ Recur down the tree, placing the value in the left or right subtree based on comparison
with the current node’s value.
◦ If the tree is empty, create a new node and place it at the current position.
3 In-Order Traversal: Write a function to perform an in-order traversal of the BST. This
function will:

◦ Visit the left subtree.


◦ Visit the current node.
◦ Visit the right subtree.
◦ Collect the values in a list.
4 Tree Sort Function: Combine the above steps into the main sorting function:
◦ Initialize the BST.
◦ Insert all elements from the input list into the BST.
◦ Perform an in-order traversal of the BST to get the sorted elements.
5 Return the Sorted List.

Python Implementation:

python
Copy code
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def insert(root, value):


"""Insert a value into the binary search tree."""
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root

def in_order_traversal(root, sorted_list):


"""Perform in-order traversal and collect values in
sorted_list."""
if root is not None:
in_order_traversal(root.left, sorted_list)
sorted_list.append(root.value)
in_order_traversal(root.right, sorted_list)

def binary_tree_sort(input_list):
"""Sort the input list using binary tree sort."""
if not input_list:
return []

# Initialize the BST


root = None

# Insert each element into the BST


for value in input_list:
root = insert(root, value)
# Retrieve the elements in sorted order
sorted_list = []
in_order_traversal(root, sorted_list)

return sorted_list

# Example usage
input_list = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_list = binary_tree_sort(input_list)
print(sorted_list) # Output: [1, 1, 2, 3, 4, 5, 5, 6, 9]
Explanation:

• TreeNode Class:

◦ Represents each node in the BST.


◦ Stores the value and references to the left and right child nodes.
• insert Function:

◦ Recursively finds the correct place for a new value and inserts it in the tree.
◦ Ensures that smaller values go to the left and larger values go to the right.
• in_order_traversal Function:

◦ Traverses the BST in order, adding node values to the sorted_list.


◦ This traversal order guarantees that the values are added in ascending order.
• binary_tree_sort Function:

◦ Initializes the root of the BST.


◦ Inserts each value from the input list into the BST.
◦ Collects the values in sorted order using in-order traversal.
This algorithm effectively sorts the input list by exploiting the properties of the binary search
tree. The time complexity is

log

)
O(nlogn) on average, but it can degrade to

n
2
)
O(n2) in the worst case if the tree becomes unbalanced.

You might also like