Binary Tree

A normal tree lets a node have any number of children. That sounds flexible. But it makes the code messy. You never know how many children to look at. So people picked one simple shape and used it everywhere. That shape is the binary tree.

A binary tree is a tree where each node has at most two children. We call them the left child and the right child. “At most two” means a node can have zero, one, or two children. It can never have three.

🌳 A Real-World Picture

Think about a knockout tournament on TV. One final match sits at the top. That final came from two semi-final matches below it. Each semi-final came from two quarter-finals below that. So every match feeds up from exactly two matches under it. There is a left side and a right side. That is a binary tree.

That fixed “two below each one” shape is what makes binary trees so handy.

🎯 Why Only Two Children?

Two is a sweet spot. With two children you can always ask one clean question. Do I go left, or do I go right? Here is why that helps.

• Your code stays simple. You only ever check two links, not a whole list of them.
• It fits decisions naturally. A yes/no question sends you to one of two sides.
• It is enough to build big ideas. Search trees, heaps, and expression trees all sit on top of this one shape.

🧱 What One Node Looks Like

Every node in a binary tree holds three things.

• data — the value stored in the node, like a number or a name.
• left — a link to the left child node, or empty if there is none.
• right — a link to the right child node, or empty if there is none.

When a link points to nothing, we call it null. In C and C++ it is NULL. In Java it is null. In Python it is None. A node with both links empty sits at the bottom. We call that a leaf node.

🗺️ The Tree We Will Build

Let us build this small tree. The value 10 sits at the top. That top node is called the root. The root has 20 as its left child and 30 as its right child.

Here 10 is the root. Both 20 and 30 are leaf nodes. Neither of them has children yet.

🪜 Steps to Build a Binary Tree

Before we write code, let us list the plan in plain words. Every language below follows these same steps.

1. Define a node type that holds data, left, and right.
2. Create the root node with the value 10. Set its left and right links to empty for now.
3. Create a node for 20. Link it as the root’s left child.
4. Create a node for 30. Link it as the root’s right child.
5. Print the root’s value, then its left child’s value, then its right child’s value.

💻 Building the Tree in Code

Now the same five steps turned into real code. Read the comments to follow along.

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

// One node holds data and two links
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

// Helper to make a new node with empty links
struct Node* newNode(int value) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct Node* root = newNode(10);   // step 2: root
    root->left = newNode(20);          // step 3: left child
    root->right = newNode(30);         // step 4: right child

    // step 5: print root and its two children
    printf("Root: %d\n", root->data);
    printf("Left child: %d\n", root->left->data);
    printf("Right child: %d\n", root->right->data);
    return 0;
}

Root: 10
Left child: 20
Right child: 30

#include <iostream>
using namespace std;

// One node holds data and two links
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Helper to make a new node with empty links
Node* newNode(int value) {
    Node* node = new Node();
    node->data = value;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

int main() {
    Node* root = newNode(10);   // step 2: root
    root->left = newNode(20);   // step 3: left child
    root->right = newNode(30);  // step 4: right child

    // step 5: print root and its two children
    cout << "Root: " << root->data << endl;
    cout << "Left child: " << root->left->data << endl;
    cout << "Right child: " << root->right->data << endl;
    return 0;
}

Root: 10
Left child: 20
Right child: 30

public class BinaryTree {
    // One node holds data and two links
    static class Node {
        int data;
        Node left;
        Node right;

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

    public static void main(String[] args) {
        Node root = new Node(10);    // step 2: root
        root.left = new Node(20);    // step 3: left child
        root.right = new Node(30);   // step 4: right child

        // step 5: print root and its two children
        System.out.println("Root: " + root.data);
        System.out.println("Left child: " + root.left.data);
        System.out.println("Right child: " + root.right.data);
    }
}

Root: 10
Left child: 20
Right child: 30

# One node holds data and two links
class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

root = Node(10)        # step 2: root
root.left = Node(20)   # step 3: left child
root.right = Node(30)  # step 4: right child

# step 5: print root and its two children
print("Root:", root.data)
print("Left child:", root.left.data)
print("Right child:", root.right.data)

Root: 10
Left child: 20
Right child: 30

// One node holds data and two links
class Node {
  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(10);      // step 2: root
root.left = new Node(20);       // step 3: left child
root.right = new Node(30);      // step 4: right child

// step 5: print root and its two children
console.log("Root:", root.data);
console.log("Left child:", root.left.data);
console.log("Right child:", root.right.data);

Root: 10
Left child: 20
Right child: 30

🧩 Common Types of Binary Trees

As trees grow, people gave names to the shapes they take. You will hear these words a lot. So let us meet them quickly.

• A full binary tree is one where every node has either zero children or exactly two children. No node is allowed to have just one child.
• A complete binary tree is filled level by level from the top. Each level fills from left to right. No gaps are left behind.
• A balanced binary tree keeps the left and right sides close to the same height. So the tree stays short and fast to search.

Here is a quick side-by-side so the difference is easy to see.

⚠️ Common Mistakes

A few small slips trip up almost everyone at the start. Watch for these.

• Forgetting to set left and right to empty when you make a node. Then they hold garbage and your code may crash.
• Reading root.left.data when left is empty. Always check the link is not null before you follow it.
• Mixing up left and right when you link children. The tree still builds, but the shape is wrong.
• Thinking every node must have two children. It can have zero, one, or two.

🧩 What You’ve Learned

• ✅ A binary tree is a tree where each node has at most two children, a left and a right.
• ✅ Two children keeps the code simple and fits yes/no style decisions.
• ✅ A node stores data, a left link, and a right link, with empty links shown as null.
• ✅ You built a small tree with 10 at the root, 20 on the left, and 30 on the right, in five languages.
• ✅ Full, complete, and balanced are common named shapes you will study later.

🚀 What’s Next?

• Tree Traversals
• Introduction to Binary Search Trees