• Hajipur, Bihar, 844101

☰
❮
❯

Python

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

Python Binary Search Trees

← Previous Next →

A Binary Search Tree (BST) is a special type of binary tree where:

  • Left subtree has values less than the node

  • Right subtree has values greater than the node

  • No duplicate values are allowed

This structure allows fast searching, insertion, and deletion in O(log n) time (in a balanced tree).

🔹 BST Node in Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

🔹 Inserting into a BST

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root
Example: Create BST
root = Node(50)
insert(root, 30)
insert(root, 70)
insert(root, 20)
insert(root, 40)
insert(root, 60)
insert(root, 80)

✅ Structure:

       50
     /    \
   30      70
  /  \    /  \
20  40  60  80

🔹 Searching in a BST

def search(root, key):
    if root is None or root.data == key:
        return root
    if key < root.data:
        return search(root.left, key)
    return search(root.right, key)

🔹 Inorder Traversal (Sorted Output)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=' ')
        inorder(root.right)

✅ Output for above tree: 20 30 40 50 60 70 80

🔹 Deleting from a BST

def delete(root, key):
    if root is None:
        return root
    if key < root.data:
        root.left = delete(root.left, key)
    elif key > root.data:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = find_min(root.right)
        root.data = temp.data
        root.right = delete(root.right, temp.data)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

🔹 Use Cases of BST

  • Fast search (like a dictionary)

  • Auto-sorted data

  • Range queries

  • Indexing in databases

  • Symbol tables

Practice Questions

Q1. Write a Python program to build a Binary Search Tree (BST) with values: 10, 5, 20, 3, 7, 15, 30.

Q2. Write a Python program to search for the value 15 in the BST.

Q3. Write a Python program to perform an Inorder traversal of the BST and print the result.

Q4. Write a Python program to delete the value 5 from the BST and print the updated tree (Inorder).

Q5. Write a Python program to insert values from a list into the BST.

Q6. Write a Python program to find the smallest value in the BST.

Q7. Write a Python program to count all the leaf nodes in the BST.

Q8. Write a Python program to print all values greater than 10 in the BST.

Q9. Write a Python program to check if a binary tree is a valid BST.

Q10. Write a Python program to find and print the height of the BST.

Python Binary Search Trees Quiz

Q1: What is the main property of a BST?

A. Root > Children
B. Left < Root < Right
C. All values equal
D. Sorted arrays only

Q2: In BST, where are smaller values stored?

A. Right
B. Left
C. Root
D. Leaf

Q3: Which traversal gives sorted values in BST?

A. Preorder
B. Postorder
C. Inorder
D. Level Order

Q4: Time complexity of search in balanced BST?

A. O(n)
B. O(log n)
C. O(n log n)
D. O(1)

Q5: Which function finds the smallest value in BST?

A. find_max()
B. traverse()
C. find_min()
D. search()

Q6: Can a Binary Search Tree (BST) have duplicate keys?

A. Yes
B. No
C. Only if inserted in left subtree
D. Only in balanced BSTs

Q7: In a Binary Search Tree (BST), where is the maximum value stored?

A. Leftmost node
B. Rightmost node
C. Root node
D. Any leaf node

Q8: Which operation is NOT valid in BST?

A. Insert
B. Delete
C. Hash
D. Search

Q9: What does inorder() return in BST?

A. Tree height
B. Sorted list
C. Random values
D. Reversed values

Q10: Which traversal visits root first?

A. Inorder
B. Preorder
C. Postorder
D. Level Order
← Previous Next →
Login
Go Back Top