Check if a value exists in a Binary Tree

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:

``````

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: