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:

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

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.