💡 Problem Formulation: In the context of binary search trees (BSTs), an internal node is any node that has at least one child. This article is aimed at discussing various methods to verify if each internal node in a BST has exactly one child. This specific condition means the BST is a degenerate (or pathological) tree, where every internal node has only one child, causing the tree to resemble a linked list. An example input would be a BST object, and the desired output is a Boolean indicating whether the BST fulfills the “one child” criterion.
Method 1: Recursive Tree Traversal
This method employs a recursive traversal of the BST. The function, has_only_one_child(node), checks if the binary tree rooted at the given node has this property by exploring its subtrees. It’s a depth-first approach that examines the child nodes of each internal node and ensures that there is exactly one child for each node checked.
Here’s an example:
def has_only_one_child(node):
if node is None or (node.left is None and node.right is None):
return True
if node.left is None or node.right is None:
return has_only_one_child(node.left) or has_only_one_child(node.right)
return False
# Example usage:
# Assuming 'root' is the root node of a BST
print(has_only_one_child(root))Output: True or False, depending on the tree’s structure.
This code snippet defines a function to check if all internal nodes have exactly one child using recursion. It returns True if the node is a leaf or has one child and that child itself satisfies the same property. If the node has two children, it returns False.
Method 2: Iterative In-order Traversal
In this strategy, an iterative in-order traversal is performed using a stack. While traversing, the code checks node structure and ensures each visited internal node does not have two children. This method is practical since it iteratively checks each node without the overhead of recursive function calls.
Here’s an example:
def has_one_child_iteratively(root):
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if current.left and current.right:
return False
current = current.right if current.right else current.left
return True
# Example usage:
print(has_one_child_iteratively(root))Output: True or False.
This snippet iterates over the BST nodes while keeping track of the traversal using a stack. For each internal node, it checks if both children are present. If so, it returns False; otherwise, it continues until all nodes are processed.
Method 3: Leveraging the Properties of BST
This method uses the fact that for any internal node with only one child, the child must either be all greater than or all less than its ancestor nodes. By checking the preorder traversal of the nodes, we can verify this property.
Here’s an example:
def has_only_one_child_preorder(preorder):
min_val, max_val = float('-inf'), float('inf')
for value in preorder:
if value max_val:
return False
if value > preorder[0]:
min_val = value
else:
max_val = value
return True
# Example usage:
preorder = [20, 10, 11, 13, 12]
print(has_only_one_child_preorder(preorder))Output: True
The code snippet takes a list of node values as a pre-order traversal of a BST. It iterates through the list and updates the minimum and maximum allowable values for the next child based on traversal history, ensuring the BST property and the “one child” constraint are met.
Method 4: Checking Sibling Presence
This method ascertains the existence of at most one sibling for each node in the BST. While traversing, the algorithm checks each node’s siblings by confirming if either left or right is None.
Here’s an example:
def check_single_child_nodes(node):
if not node or (node.left is None and node.right is None):
return True
if node.left and node.right:
return False
return (check_single_child_nodes(node.left)
if node.left else
check_single_child_nodes(node.right))
# Example usage:
print(check_single_child_nodes(root))Output: True or False.
In this snippet, the function check_single_child_nodes traverses the BST and for each node checks if it has either left or right as None, making sure that there aren’t two children. It continues to check until all nodes have been verified.
Bonus One-Liner Method 5: Using Python’s All Function
We can compact the recursion into a one-liner using Python’s powerful all() function, combined with a generator expression to check if all nodes meet the one-child condition.
Here’s an example:
check_single_child = lambda x: True if x is None else False if x.left and x.right else check_single_child(x.left) or check_single_child(x.right) # Example usage: print(check_single_child(root))
Output: True or False.
This one-liner uses a lambda function to recursively check if a node fulfills the condition of having exactly one child or being a leaf. It encapsulates the recursive logic in a concise manner.
Summary/Discussion
- Method 1: Recursive Tree Traversal. This method is simple to understand and implement but may suffer from stack overflows with very deep trees due to the nature of recursive calls.
- Method 2: Iterative In-order Traversal. Iteration avoids the stack overflow issue and is generally more efficient than recursion. However, it is slightly more complex due to the explicit stack management.
- Method 3: Leveraging the Properties of BST. Very efficient as it does not require tree traversal and works directly on the preorder list of node values. Though, it assumes that the tree’s preorder traversal is readily available.
- Method 4: Checking Sibling Presence. Does not require additional data structures and clearly checks the sibling condition, but like the first method, it is recursive and can overflow on deep trees.
- Bonus Method 5: Using Python’s All Function. This functional approach is terse and may appeal to those who favor functional programming paradigms, but it can be less readable for some users.