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


#include <stdio.h>
#include <stdlib.h>

struct Node {
    int value;
    struct Node* left;
    struct Node* right;
};

// Function to create and return a new node
struct Node* createNode(int value) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}


#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;

    Node(int val) : value(val), left(nullptr), right(nullptr) {}
};


class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}


class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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)


#include <stdio.h>
#include <stdlib.h>

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Node* createFullBinaryTree() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    return root;
}

int main() {
    struct Node* root = createFullBinaryTree();
    printf("Root value: %d\n", root->value);
    // Remember to delete all the nodes!!
    return 0;
}


#include <iostream>
#include <memory>

std::unique_ptr<Node> createFullBinaryTree() {
    std::unique_ptr<Node> root = std::make_unique<Node>(1);
    root->left = std::make_unique<Node>(2);
    root->right = std::make_unique<Node>(3);
    root->left->left = std::make_unique<Node>(4);
    root->left->right = std::make_unique<Node>(5);
    root->right->left = std::make_unique<Node>(6);
    root->right->right = std::make_unique<Node>(7);
    return root;
}

int main() {
    std::unique_ptr<Node> root = createFullBinaryTree();
    std::cout << "Root value: " << root->value << std::endl;
    return 0;
}


function createFullBinaryTree() {
    let root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    return root;
}

let root = createFullBinaryTree();
console.log("Root value: " + root.value);


Node createFullBinaryTree() {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    return root;
}

public class Main {
    public static void main(String[] args) {
        Node root = createFullBinaryTree();
        System.out.println("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.