Mastering Binary Search Trees in Python

Introduction

This challenge is about implementing a binary search tree with an insert method in Python.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") algorithm/BasicAlgorithmsGroup -.-> algorithm/recursion_dynamic("`Recursion Dynamic`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/BasicConceptsGroup -.-> python/type_conversion("`Type Conversion`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/graphs_trees -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} algorithm/recursion_dynamic -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/variables_data_types -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/strings -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/type_conversion -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/conditional_statements -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/tuples -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/function_definition -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/default_arguments -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/classes_objects -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/constructor -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/polymorphism -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/encapsulation -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/raising_exceptions -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} python/build_in_functions -.-> lab-268823{{"`Binary Search Tree Implementation in Python`"}} end

Bst

Problem

A binary search tree is a data structure that allows fast search, insert, and delete operations. It is a tree where each node has at most two children, and the left child is less than the parent, and the right child is greater than the parent. The insert method adds a new node to the tree in the appropriate position based on its value.

Your task is to implement a binary search tree with an insert method in Python. The insert method should take a value and add a new node to the tree in the appropriate position based on its value. If the root input is None, return a tree with the only element being the new root node.

Requirements

To complete this challenge, you need to meet the following requirements:

You cannot insert None values.

You can assume you are working with valid integers.

You can assume all left descendents are less than or equal to the node, and all right descendents are greater than the node.

You do not have to keep track of the parent nodes, but it is optional.

You can assume this fits in memory.

Example Usage

Insert

Insert will be tested through the following traversal:

In-Order Traversal

5, 2, 8, 1, 3 -> 1, 2, 3, 5, 8

1, 2, 3, 4, 5 -> 1, 2, 3, 4, 5

You do not have to code the in-order traversal, it is part of the unit test.

Binary Search Tree Implementation in Python