Binary Tree — Data Structure & Algrorithm

A binary tree is a type of tree data structure where each node can have at most two children.

These two children are called:

Left Child
Right Child

For example:

Here, 10 has two children: 20 and 30.

Node 20 also has two children: 40 and 50.

Node 30 has no children.

The important rule is:

A node in a binary tree can have zero, one, or two children, but never more than two.

What is a Binary Tree?

A binary tree consists of nodes connected through parent-child relationships.

Each node can contain:

Data
Left Child
Right Child

For example:

        10
       /  \
      20   30

The node 10 is the parent, while 20 and 30 are its children.

A node doesn't have to have two children.

For example:

        10
       /
      20

This is also a valid binary tree.

And even this is valid:

A tree containing only one node is still a binary tree.

Creating a Binary Tree Node in Java

A binary tree node can be represented using a class:

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

    Node(int data) {
        this.data = data;
    }
}

Here:

data  → stores the value
left  → points to the left child
right → points to the right child

Initially, left and right are null.

Creating a Binary Tree

Suppose we want to create this tree:

We can create it in Java:

Node root = new Node(10);

root.left = new Node(20);
root.right = new Node(30);

root.left.left = new Node(40);
root.left.right = new Node(50);

The root variable points to the first node:

root
 ↓
10

From 10, we can reach every other node.

Root Node

The topmost node is called the root.

In:

        10
       /  \
      20   30

10 is the root.

A binary tree has only one root.

Leaf Nodes

A node with no children is called a leaf node.

For:

the leaf nodes are:

40
50
30

They don't have either a left or right child.

Parent and Child

Consider:

        10
       /  \
      20   30

Here:

10 → Parent
20 → Left Child
30 → Right Child

Similarly, in:

      20
     /  \
    40   50

20 is the parent of 40 and 50.

Height of a Binary Tree

The height of a binary tree is the length of the longest path from the root to a leaf.

Consider:

The longest path is:

10 → 20 → 40

If height is measured by the number of edges, the height is 2.

The exact definition can sometimes differ between textbooks, so always check whether height is being counted in edges or nodes.

Depth of a Node

The depth of a node is its distance from the root.

For example:

              10       Depth 0
             /  \
            20   30    Depth 1
           /
          40           Depth 2

So:

The root always has depth 0 when depth is measured by edges.

Types of Binary Trees

There are several important types of binary trees.

The most common ones you'll encounter are:

Full Binary Tree
Complete Binary Tree
Perfect Binary Tree
Balanced Binary Tree
Skewed Binary Tree

Understanding these structures is important because their shape affects how efficiently we can perform operations.

Full Binary Tree

A full binary tree is a binary tree where every node has either:

0 children
or
2 children

No node has exactly one child.

For example:

This is a full binary tree.

But:

        10
       /
      20

is not full because 10 has only one child.

Complete Binary Tree

A complete binary tree has all levels completely filled except possibly the last level.

The nodes in the last level are filled from left to right.

For example:

This is a complete binary tree.

But:

is not complete because the nodes are not filled from left to right.

Complete binary trees are particularly important when studying heaps.

Perfect Binary Tree

A perfect binary tree is a binary tree where:

Every internal node has exactly two children.
Every leaf is at the same level.

For example:

          10
        /    \
       20     30
      /  \   /  \
     40  50 60  70

Every level is completely filled.

For a perfect binary tree with height h, the number of nodes is:

2^(h + 1) - 1

when height is measured in edges.

Balanced Binary Tree

A balanced binary tree is a tree whose height is kept relatively small compared with the number of nodes.

For example:

          50
        /    \
       30     70
      /  \   /  \
     20  40 60  80

The tree is relatively evenly distributed.

A highly unbalanced tree could look like:

The second structure has a much greater height.

Balance becomes especially important in Binary Search Trees because it affects search performance.

Skewed Binary Tree

A skewed binary tree is a tree where nodes mostly have children on only one side.

A left-skewed tree:

A right-skewed tree:

These structures behave similarly to linked lists.

Binary Tree Traversals

One of the most important things you'll learn with binary trees is traversal.

Traversal means visiting every node in a particular order.

The major traversals are:

Preorder
Inorder
Postorder
Level Order

Consider this tree:

Preorder Traversal

Preorder follows:

Root → Left → Right

So the traversal is:

10 → 20 → 40 → 50 → 30

In Java:

static void preorder(Node root) {

    if (root == null) {
        return;
    }

    System.out.print(root.data + " ");

    preorder(root.left);
    preorder(root.right);
}

The first thing we do is process the current node.

Then we recursively process the left subtree and right subtree.

Inorder Traversal

Inorder follows:

Left → Root → Right

For our tree:

the result is:

40 → 20 → 50 → 10 → 30

Java implementation:

static void inorder(Node root) {

    if (root == null) {
        return;
    }

    inorder(root.left);

    System.out.print(root.data + " ");

    inorder(root.right);
}

Inorder traversal is particularly important for Binary Search Trees, where it produces the values in sorted order.

Postorder Traversal

Postorder follows:

Left → Right → Root

For our tree:

the result is:

40 → 50 → 20 → 30 → 10

Java implementation:

static void postorder(Node root) {

    if (root == null) {
        return;
    }

    postorder(root.left);
    postorder(root.right);

    System.out.print(root.data + " ");
}

Postorder is useful in problems where we need to process children before their parent.

Level Order Traversal

Level order visits nodes level by level.

For:

the result is:

10 → 20 → 30 → 40 → 50

A queue is commonly used:

import java.util.LinkedList;
import java.util.Queue;

static void levelOrder(Node root) {

    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();

    queue.add(root);

    while (!queue.isEmpty()) {

        Node current = queue.remove();

        System.out.print(current.data + " ");

        if (current.left != null) {
            queue.add(current.left);
        }

        if (current.right != null) {
            queue.add(current.right);
        }
    }
}

The queue keeps track of which nodes should be processed next.

Binary Tree and Recursion

Binary trees and recursion work extremely well together.

Why?

Because every node can have a left subtree and a right subtree.

For example:

        10
       /  \
      20   30

The tree can be thought of as:

Root
├── Left Subtree
└── Right Subtree

And each subtree is itself a smaller binary tree.

That's why many binary tree algorithms follow this pattern:

if (root == null) {
    return;
}

solve(root.left);
solve(root.right);

This recursive structure makes many tree problems much easier to express.

Finding the Number of Nodes

We can recursively count the nodes.

static int countNodes(Node root) {

    if (root == null) {
        return 0;
    }

    return 1
        + countNodes(root.left)
        + countNodes(root.right);
}

For:

the result is:

The 1 represents the current node, while the recursive calls count nodes in the left and right subtrees.

Finding the Maximum Value

We can also find the largest value recursively:

static int findMax(Node root) {

    if (root == null) {
        return Integer.MIN_VALUE;
    }

    int leftMax = findMax(root.left);
    int rightMax = findMax(root.right);

    return Math.max(
        root.data,
        Math.max(leftMax, rightMax)
    );
}

For:

the result is:

This requires visiting every node, so the time complexity is O(n).

Binary Tree vs Binary Search Tree

These two terms are easy to confuse.

A binary tree only has one main structural rule:

Each node can have at most two children.

There is no requirement that values be sorted.

For example:

        50
       /  \
      80   20

This is still a valid binary tree.

A Binary Search Tree has an additional ordering rule:

Left < Root < Right

For example:

        50
       /  \
      30   70

Here, 30 < 50 < 70.

So:

Binary Tree
→ Structural rule

Binary Search Tree
→ Structural rule + Ordering rule

Time Complexity

If we need to visit every node in a binary tree, the time complexity is:

O(n)

because there are n nodes.

For example, preorder traversal:

Time: O(n)

Inorder:

Time: O(n)

Postorder:

Time: O(n)

Level order:

Time: O(n)

Each traversal visits every node once.

The recursive traversals also use space proportional to the tree's height because of the call stack:

Space: O(h)

where h is the height of the tree.

For a balanced tree, this is around O(log n).

For a completely skewed tree, it can become O(n).

Real-Life Example

Think about a company's organizational structure:

             CEO
            /   \
      Manager   Manager
       /  \       \
     John Jason    Alex

Each person can have multiple employees in a general hierarchy, but if we limit each person to at most two direct reports, we get a structure that behaves like a binary tree.

Binary trees are especially useful when a problem naturally involves making two possible branches.

For example:

             Decision
             /      \
           Yes       No

Each decision can lead to another decision, creating a tree of possibilities.

Applications of Binary Trees

Binary trees are used as the foundation for many important data structures and algorithms, including:

Binary Search Trees
Heaps
Expression Trees
Decision Trees
Syntax Trees
File and directory structures
Searching algorithms
Tree traversal algorithms

Many advanced tree structures are built by adding additional rules to the basic binary tree.

A Complete Example

Let's create a binary tree and perform all three depth-first traversals:

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

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static void preorder(Node root) {

        if (root == null) {
            return;
        }

        System.out.print(root.data + " ");

        preorder(root.left);
        preorder(root.right);
    }

    static void inorder(Node root) {

        if (root == null) {
            return;
        }

        inorder(root.left);

        System.out.print(root.data + " ");

        inorder(root.right);
    }

    static void postorder(Node root) {

        if (root == null) {
            return;
        }

        postorder(root.left);
        postorder(root.right);

        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {

        Node root = new Node(10);

        root.left = new Node(20);
        root.right = new Node(30);

        root.left.left = new Node(40);
        root.left.right = new Node(50);

        System.out.print("Preorder: ");
        preorder(root);

        System.out.print("\nInorder: ");
        inorder(root);

        System.out.print("\nPostorder: ");
        postorder(root);
    }
}

Output:

Preorder: 10 20 40 50 30
Inorder: 40 20 50 10 30
Postorder: 40 50 20 30 10

The key to understanding these traversals is simply remembering where the root is processed:

Preorder  → Root, Left, Right
Inorder   → Left, Root, Right
Postorder → Left, Right, Root

The Main Idea

A binary tree is a tree in which every node can have at most two children:

        Node
       /    \
    Left   Right

The most important concepts are:

Root
Parent
Child
Leaf
Height
Depth
Preorder
Inorder
Postorder
Level Order

And remember the key distinction:

A binary tree only limits each node to at most two children. It does not require the values to be sorted.

That ordering rule belongs to the Binary Search Tree, which is the next important concept built on top of the binary tree.