Creating a Binary Tree

Binary Tree

When building a binary tree, a common beginner-friendly method is to read values in preorder format. In preorder, we read:

Preorder Format

To represent no child, we use a sentinel value (commonly -1).
Whenever the program reads -1, it returns null, meaning no node exists there.

Example Input

Let’s say we enter the following values:

10 20 30 -1 -1 40 50 -1 60 -1 -1 70 -1 -1

How this input builds the tree
10 → root
20 → left child of 10
30 → left child of 20
-1 -1 → 30 has no children
40 → right child of 20
50 → left child of 40
-1 → no left child for 50
60 → right child of 50
-1 -1 → 60 has no children
70 → right child of 40
-1 -1 → 70 has no children

Get Suraj Kachate’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The resulting tree

Binary Tree

The Idea Behind the Code

The createTree function first reads a value from the input. If the value is -1, it means there is no node at that position, so the function returns null. Otherwise, it creates a new node with the given value. Then, it recursively calls itself to build the left subtree, followed by the right subtree. This process continues until the entire tree is constructed. After building the tree, a traversal method like inorder traversal is used to display the nodes, which is simply a way to visit each node in a specific order.

Pseudocode

function createTree():
    read value
    if value == -1:
        return NULL
    node = new Node(value)
    node.left = createTree()
    node.right = createTree()
    return node

Flowchart

Flowchart for createTree function

Pause. Solve it. Then scroll for the answer.

Code

JAVA

import java.util.Scanner;

class Node{
    int data;
    Node left;
    Node right;

    Node(int val){
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

public class BinaryTree {

    public Node createTree(Scanner sc){
        int val = sc.nextInt();
        if(val == -1) return null;

        Node root = new Node(val);
        root.left = createTree(sc);
        root.right = createTree(sc);
        return root;
    }

    void inorder(Node root){
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.data + " ");
        inorder(root.right);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        BinaryTree tree = new BinaryTree();
        Node root = tree.createTree(sc);
        tree.inorder(root);
        sc.close();
    }
}

C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* createTree() {
    int val;
    cin >> val;

    if(val == -1) return nullptr;

    Node* root = new Node(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

void inorder(Node* root) {
    if(root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = createTree();
    inorder(root);
    return 0;
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def create_tree(values):
    val = next(values)
    if val == -1:
        return None

    node = Node(val)
    node.left = create_tree(values)
    node.right = create_tree(values)
    return node

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

values = iter(map(int, input().split()))
root = create_tree(values)
inorder(root)

C

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createTree() {
    int val;
    scanf("%d", &val);

    if (val == -1) return NULL;

    struct Node* root = (struct Node*)malloc(sizeof(struct Node));
    root->data = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

void inorder(struct Node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main(){
    struct Node* root = createTree();
    inorder(root);
    return 0;
}