basic binary tree Algorithm
They let fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that let finding an item by its key (e.g., finding the telephone number of a person by name).Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, make comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees.
class Node:
"""
This is the Class Node with a constructor that contains data variable to type data
and left, right pointers.
"""
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def display(tree): # In Order traversal of the tree
if tree is None:
return
if tree.left is not None:
display(tree.left)
print(tree.data)
if tree.right is not None:
display(tree.right)
return
def depth_of_tree(
tree,
): # This is the recursive function to find the depth of binary tree.
if tree is None:
return 0
else:
depth_l_tree = depth_of_tree(tree.left)
depth_r_tree = depth_of_tree(tree.right)
if depth_l_tree > depth_r_tree:
return 1 + depth_l_tree
else:
return 1 + depth_r_tree
def is_full_binary_tree(
tree,
): # This function returns that is it full binary tree or not?
if tree is None:
return True
if (tree.left is None) and (tree.right is None):
return True
if (tree.left is not None) and (tree.right is not None):
return is_full_binary_tree(tree.left) and is_full_binary_tree(tree.right)
else:
return False
def main(): # Main function for testing.
tree = Node(1)
tree.left = Node(2)
tree.right = Node(3)
tree.left.left = Node(4)
tree.left.right = Node(5)
tree.left.right.left = Node(6)
tree.right.left = Node(7)
tree.right.left.left = Node(8)
tree.right.left.left.right = Node(9)
print(is_full_binary_tree(tree))
print(depth_of_tree(tree))
print("Tree is: ")
display(tree)
if __name__ == "__main__":
main()
