π‘ 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.