Day 23 - Python - New Year Featured!

on

We are back with a bang for this New Year! Let's continue daily and learn a Python and Java program continuously as planned! 

Python for a day, Java for another, let's reach our target of 100 days of Coding successfully! 

Happy New Year learners! Happy 2025! 

Problem Statement

You are tasked with organizing and searching New Year's resolutions. Write a Python program that uses a Binary Search Tree (BST) to:

  1. Insert the given resolutions into the BST.
  2. Search for a specific resolution in the BST.
  3. Display all resolutions in lexicographical order.

The resolutions will be provided as a single string, with individual resolutions separated by the | character.

Function Description

Complete the following functions:

  1. insert(root, key)

    • Inserts a resolution (key) into the BST rooted at root.
    • Returns the root of the updated BST.

  2. search(root, key)

    • Searches for a specific resolution (key) in the BST rooted at root.
    • Returns True if the resolution exists, otherwise returns False.

  3. inorder(root)

    • Performs an in-order traversal of the BST and returns a list of resolutions in lexicographical order.

  4. main()

    • Parses input, builds the BST, performs a search, and displays the results.

Input Format

  1. A single string containing resolutions separated by the | character.
    Example: "Exercise more|Read more books|Learn Python|Save money|Travel the world|Be more organized"
  2. A single string specifying the resolution to search for.
    Example: "Learn Python"

Output Format

  1. Print whether the searched resolution exists in the BST.
    Format:
    "Searching for '<resolution>': Found!"
    or
    "Searching for '<resolution>': Not found."
  2. Print all resolutions in sorted order under the title:
    "New Year's Resolutions in Sorted Order:"
    Each resolution should be prefixed with -.

Sample Test Cases

Sample Input 1

Exercise more|Read more books|Learn Python|Save money|Travel the world|Be more organized
Learn Python

Sample Output 1

Searching for 'Learn Python': Found!

New Year's Resolutions in Sorted Order:
- Be more organized
- Exercise more
- Learn Python
- Read more books
- Save money
- Travel the world

Sample Input 2

Wake up early|Eat healthy|Work smarter
Exercise more

Sample Output 2

Searching for 'Exercise more': Not found.

New Year's Resolutions in Sorted Order:
- Eat healthy
- Wake up early
- Work smarter

Sample Input 3

Travel to Himalayas|Write a book|Meditate daily
Write a book

Sample Output 3

Searching for 'Write a book': Found!

New Year's Resolutions in Sorted Order:
- Meditate daily
- Travel to Himalayas
- Write a book

Constraints

  1. The input string of resolutions will not be empty.
  2. Resolutions are case-sensitive.
  3. The number of resolutions (n) will not exceed 100.

Python Code

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, root, key):
        if root is None:
            return Node(key)
        if key < root.key:
            root.left = self.insert(root.left, key)
        elif key > root.key:
            root.right = self.insert(root.right, key)
        return root

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

    def inorder(self, root, result):
        if root:
            self.inorder(root.left, result)
            result.append(root.key)
            self.inorder(root.right, result)
        return result

def main():
    resolutions = input("Enter resolutions separated by '|': ").strip().split("|")
    
    search_query = input("Enter the resolution to search for: ").strip()

    bst = BST()
    root = None
    for resolution in resolutions:
        root = bst.insert(root, resolution.strip())

    found = bst.search(root, search_query)
    print(f"Searching for '{search_query}':", "Found!" if found else "Not found.")

    print("\nNew Year's Resolutions in Sorted Order:")
    sorted_resolutions = bst.inorder(root, [])
    for res in sorted_resolutions:
        print("- " + res)

if __name__ == "__main__":
    main()

Insights

  1. Modular Design: The code is well-structured with separate classes for Node and BST and a main() function for input handling and orchestration.
  2. Efficient Data Structure: Uses a Binary Search Tree (BST) for storing resolutions, ensuring efficient operations like insertion and search.
  3. Insertion Logic: The insert method maintains BST properties and avoids duplicates naturally by design.
  4. Search Method: Recursively checks for a resolution, providing O(log n) complexity for average cases.
  5. In-Order Traversal: Returns resolutions in lexicographical order, leveraging the BST structure.
  6. Input Parsing: Parses resolutions from a single string using | as a delimiter, simplifying user input.
  7. Output Formatting: Provides user-friendly messages for search results and outputs resolutions as a neatly formatted list.
  8. Case Sensitivity: Resolutions are treated as case-sensitive, differentiating between "Exercise" and "exercise."
  9. Edge Case Resilience: Handles empty trees gracefully and ignores duplicate resolutions during insertion.
  10. Scalability Concerns: Efficient for moderate input sizes but could degrade to O(n) in worst-case scenarios (e.g., unbalanced BST).
🎉 Wishing all our Learners a Happy New Year filled with curiosity and growth! 🚀 Embrace challenges, keep coding, and let each bug teach you something new—2025 is yours to conquer! 🌟

Comments

Post a Comment