💡 Problem Formulation: Finding the median of a Binary Search Tree (BST) in linear time and constant space is a significant challenge, as the median is the middle element when the elements are sorted, and a BST allows in-order traversal, which naturally orders the elements. The task is to find the median value without consuming extra space for array storage, even covertly, and to do it efficiently within a single traversal of the BST. For example, a BST with elements [1, 2, 3, 4, 5] has a median value of 3.
Method 1: Morris In-order Traversal
This method utilizes Morris traversal to find the median of a BST. Morris traversal allows us to perform an in-order traversal without using recursion or a stack, thus achieving O(1) space complexity. During traversal, we can count nodes and find the median accordingly, dealing with both even and odd numbers of nodes in the tree.
Here’s an example:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.val = value
self.left = left
self.right = right
def findMedian(root):
def countNodes(node):
count = 0
current = node
while current:
count += 1
current = current.right if current.right else current.left
return count
total_nodes = countNodes(root)
count = 0
current = root
prev = None
median = None
while current:
if current.left:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if not pre.right:
pre.right = current
current = current.left
else:
pre.right = None
count += 1
if total_nodes % 2 != 0 and count == (total_nodes + 1) // 2:
median = current.val
break
elif total_nodes % 2 == 0 and count == total_nodes // 2:
median = (prev.val + current.val) / 2
break
prev = current
current = current.right
else:
count += 1
if total_nodes % 2 != 0 and count == (total_nodes + 1) // 2:
median = current.val
break
elif total_nodes % 2 == 0 and count == total_nodes // 2:
median = (prev.val + current.val) / 2
break
prev = current
current = current.right
return median
The output of the code snippet will depend on the input BST. For a BST with nodes [1, 2, 3, 4, 5], the output will be:
3
The example provided demonstrates Morris in-order traversal for finding the median of a BST. The traversal replaces the right null pointers of the tree with links returning to the parent but restores them back to the original structure once traversed. It keeps track of the count of visited nodes and calculates the median by either finding the middle node or the average of the two central nodes, depending on whether the total number of nodes is odd or even.
Method 2: In-order Traversal with Node Counting
Method 3: Threaded Binary Tree
Method 4: Selective Recursive In-order Traversal
Bonus One-Liner Method 5: Functional Programming Approach
Summary/Discussion
- Method 1: Morris In-order Traversal. This is an efficient approach that uses O(1) space by modifying the tree and then restoring it as it processes each node. However, it can be complex and harder to understand at first glance.