Welcome to this comprehensive lesson on Inorder Successor and Predecessor! Let's dive into the exciting world of data structures and algorithms, and learn how to navigate binary search trees efficiently. š²
Before we delve into Inorder Successor and Predecessor, let's first understand the concept of a Binary Search Tree (BST). A BST is a tree data structure in which each node has at most two children, denoted as left and right. The left child has a key less than its parent, while the right child has a key greater than its parent.
Inorder traversal is a way to traverse a binary search tree by visiting the left subtree, the root, and then the right subtree. This method arranges the elements in a sorted order, which is a valuable feature in many real-world applications.
Now that we know about Inorder traversal, let's learn how to find the Inorder successor and predecessor of a node in a BST.
The Inorder successor of a node is the node with the next higher value in the sorted order. In a BST, if a node has a right child, its successor is the leftmost node in its right subtree. If a node does not have a right child but has a parent, its successor is its parent.
Here's a simple example:
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.right.left = Node(5)
def find_inorder_successor(node):
if node.right is not None:
return find_min(node.right)
if node.parent is not None:
if node.parent.right == node:
return node.parent
else:
return node.parent.inorder_successor
return None
def find_min(node):
current = node
while current.left is not None:
current = current.left
return currentIn the example above, if we want to find the Inorder successor of the node with key 5, the function find_inorder_successor will return the node with key 6.
The Inorder predecessor of a node is the node with the next lower value in the sorted order. In a BST, if a node has a left child, its predecessor is the rightmost node in its left subtree. If a node does not have a left child but has a parent, its predecessor is its parent.
Here's an example for finding the Inorder predecessor:
def find_inorder_predecessor(node):
if node.left is not None:
return find_max(node.left)
if node.parent is not None:
if node.parent.left == node:
return node.parent
else:
return node.parent.inorder_predecessor
return None
def find_max(node):
current = node
while current.right is not None:
current = current.right
return currentIn the example above, if we want to find the Inorder predecessor of the node with key 6, the function find_inorder_predecessor will return the node with key 5.
What is the Inorder successor of a node in a binary search tree?
What is the Inorder predecessor of a node in a binary search tree?