Binary tree representation
Binary trees are a fundamental data structure widely used in computer science. They are particularly useful for creating efficient algorithms for tasks such as searching, sorting, and traversing data.
Binary trees are composed of nodes, where each node has at most two children - a left child and a right child. Each of the left and right children can also have their left and right children, and that structure continues until there are no more nodes in the tree.
The topmost node in a binary tree is called the root, while the bottommost elements are called the leaves of the tree.
This simple idea allows representing surprisingly many different data types in an efficient manner and are easy to implement in different programming languages:
class Node: # Node object to hold the data for each node
def __init__(self, value): # The value to keep in each node (can be anything)
self.left = None # Initially both left and right are None
self.right = None
self.value = value # Hold the value in an object
# Manually create all the nodes
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# We can then recursively traverse the whole binary tree
# Let's compute the sum of all the nodes
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Return the sum of the left subtree, the right subtree, and the current node
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Prints 36In this example, we traverse all the nodes starting from the
root. If the current node is None, it means, we’ve reached the end of the subtree on that path, so we can return 0 as the sum. Otherwise, we can compute the sum of the left subtree, the right subtree, and the current node and add all of them together.Challenge: Create a binary tree manually
Given the binary tree in the picture, you are asked to manually create it.
Write a code that would create the binary tree. You don’t need to print anything. That part is handled automatically.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB