↓Skip to main content
Algorithms

Binary Trees

3 mins
Table of Contents

You Might Also Like

rainforest full of trees

What is a Binary Tree? #

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. This restriction means that a binary tree is a special type of tree, and it is not the same as a general tree.

By limiting the number of children to two, a binary tree can be represented in a more compact way than a general tree. This makes it easier to work with binary trees and to implement algorithms that use binary trees.

Binary trees are often categorized as either full, complete, or perfect. These categories are based on the structure of the tree and the properties of the nodes.

Full Binary Tree #

Every node has either 0 or 2 children. So if a node has 1 child, it is not a full binary tree.

      1
     /   \
    2     3
   / \
  4   5

Complete Binary Tree #

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Although this is an unusual definition, it is a useful data structure for efficent priority queue implementations.

      1
     /   \
    2     3
   / \   /
  4   5 6

Perfect Binary Tree #

A perfect binary tree is a binary tree in which all the internal nodes have 2 children and all the leaves are at the same level.

A perfect binary tree is also a complete binary tree, but not all complete binary trees are perfect.

      1
     /   \
    2     3
   / \   / \
  4  5  6   7

A perfect binary is symmetric and has the same number of nodes on the left and right subtrees.

Some of the properties of a perfect binary tree are:

  • The number of nodes in a perfect binary tree is 2(n+1) - 1, where n is the height of the tree.

  • The number of leaves in a perfect binary tree is 2n, where n is the height of the tree.

  • The number of internal nodes in a perfect binary tree is 2n - 1, where n is the height of the tree.

  • The height of a perfect binary tree is log2(n+1) - 1, where n is the number of nodes in the tree.

Java Implementation #

A typical binary tree is implemented using a node class that contains a data field and references to the left and right children.

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

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

An example implementation of a binary tree can be as follows.

class BinaryTree {
    Node root;

    public BinaryTree(int data) {
        root = new Node(data);
    }

    public BinaryTree() {
        root = null;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
    }
}