Binary Search Tree In-Order Successor

Introduction

In computer science, a binary search tree (BST) is a binary tree data structure in which the value of each node in the tree is greater than or equal to any value in its left subtree and less than or equal to any value in its right subtree. In this challenge, we are going to find the in-order successor of a given node in a binary search tree.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) 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`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") 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 python/comments -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} algorithm/graphs_trees -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} algorithm/recursion_dynamic -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/variables_data_types -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/strings -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/type_conversion -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/conditional_statements -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/tuples -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/function_definition -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/default_arguments -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/classes_objects -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/constructor -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/polymorphism -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/encapsulation -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/raising_exceptions -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} python/build_in_functions -.-> lab-268821{{"`Binary Search Tree In-Order Successor`"}} end

Bst Successor

Problem

Given a binary search tree and a node in it, find the in-order successor of that node. The successor of a node is the node that appears immediately after the given node in an in-order traversal of the tree. If there is no successor, return None. If the input is None, throw an exception. We can assume we already have a Node class that keeps track of parents, and we can assume this fits memory.

Requirements

The function should return the in-order successor of a given node in a binary search tree.
If there is no successor, the function should return None.
If the input is None, the function should throw an exception.
We can assume we already have a Node class that keeps track of parents.
We can assume this fits memory.

Example Usage

          _5_
        /     \
       3       8
      / \    /   \
     2   4  6    12
    /        \   / \
   1          7 10  15
               /
              9

In: None  Out: Exception
In: 4     Out: 5
In: 5     Out: 6
In: 8     Out: 9
In: 15    Out: None

Summary

In this challenge, we have learned how to find the in-order successor of a given node in a binary search tree. We have also learned the requirements of the function, including returning None if there is no successor, throwing an exception if the input is None, and assuming we already have a Node class that keeps track of parents.