Implementing Binary Tree Data Structure

A binary tree can be created by connecting multiple individual nodes together in a hierarchical fashion. Each node in the binary tree should be able to store a value/item along with two references: one reference for the left child node and the other for the right child node. If either or both of left/right child nodes are not present, these references can be blank (None in python or nullptr in C++).

Below is how we can define a basic binary node class in various languages:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None # Left Child
        self.right = None # Right Child

Let’s now use the node definition to create nodes and stitch them together to form the below binary tree:

def create_full_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

root = create_full_binary_tree()
print("Root value:", root.value)

This is what we do in the function create_full_binary_tree / createFullBinaryTree:

  • Create the root node with value 1
  • Create a node with value 2 and set it as left child node of root node
  • Create a node with value 3 and set it as right child node of root node
  • Create nodes with values 4 and 5 and set them as right and left childs of node 2 (rootnode’s left node)
  • Create nodes with values 6 and 7 and set them as right and left childs of node 3 (rootnode’s right node)
  • Now return the pointer/reference to root node

Once the binary tree is created, it can be traversed or any operations can be performed by using the root node.