We can perform any tree traversal technique like in-order, pre-order, post-order etc and check if the element is present while each node is visited. But of all traversals, pre-order traversal is more efficient as we skip traversing all the nodes in the left and right subtree if the current node’s value is equal to the value we are looking for.
Search for a value Recursively
In the recursive approach, we do a pre-order traversal: If the current node is equal to the value we are looking for, we return the node. Otherwise we search for the element in left subtree and if it is still not found, we search in the right subtree.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def find_node(root, target):
# If the node is empty (or tree is empty), return 0
if root is None:
return None
# Check if the current node contains the target value
if root.value == target:
return root
# Recursively search in the left subtree
left_result = find_node(root.left, target)
if left_result:
return left_result
# Recursively search in the right subtree
right_result = find_node(root.right, target)
if right_result:
return right_result
return None # Return None if the target value is not found
# Create a sample binary tree for testing
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Let's test the function to find a node with a specific value
if __name__ == "__main__":
tree_root = create_binary_tree()
target_value = 5
result_node = find_node(tree_root, target_value)
if result_node:
print(f"Node with value {target_value} found in the tree.")
else:
print(f"Node with value {target_value} not found in the tree.")
Search for a value Iteratively
The iterative version is similar to the recursive function. But instead of using recursive function calls using system’s stack, we use stack data structure and iteratively search in pre-order traversal fashion.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def find_node(root, target):
# If the node is empty (or tree is empty), return 0
if root is None:
return None
stack = [root]
while stack:
current = stack.pop()
# Check if the current node contains the target value
if current.value == target:
return current
# Add right and left children to the stack for further exploration
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return None # Return None if the target value is not found
# Create a sample binary tree for testing
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Let's test the function to find a node with a specific value
if __name__ == "__main__":
tree_root = create_binary_tree()
target_value = 5
result_node = find_node(tree_root, target_value)
if result_node:
print(f"Node with value {target_value} found in the tree.")
else:
print(f"Node with value {target_value} not found in the tree.")