Binary Tree Data Structure Explained

Learn Binary Tree Data Structure Explained with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Binary Tree?

A binary tree is a tree data structure in which each node has at most two children. These children are commonly called the left child and right child.

A node can therefore have zero, one, or two children. Unlike a Binary Search Tree, a general binary tree does not require values to follow a particular ordering rule. 

              10
            /    \
           5      20
         /  \       \
        3    8       25

In this example, 10 is the root. Its left child is 5 and its right child is 20. Node 5 has two children, while node 20 has only one child.

How a Binary Tree Is Structured

Each binary tree node normally stores three pieces of information: its value, a reference to the left child, and a reference to the right child. 

Node
├── value
├── left
└── right

If a node does not have a left or right child, the corresponding reference is null.

Binary Tree Example

                A
              /   \
             B     C
            / \     \
           D   E     F
              /
             G
Node Left Child Right Child
A B C
B D E
C None F
D None None
E G None

Key Characteristics of a Binary Tree

  • Each node has at most two children.
  • The children are identified as left and right children.
  • A node can have zero, one, or two children.
  • The tree can contain any type of value unless a specialized tree adds ordering rules.
  • A binary tree does not have to be balanced.
  • A binary tree does not have to be sorted.
  • A binary tree can be empty.

Binary Tree vs Binary Search Tree

A binary tree and a Binary Search Tree (BST) are not the same thing. A BST is a specialized binary tree that follows an ordering rule.

Feature Binary Tree Binary Search Tree
Maximum children 2 2
Ordering rule None required Left values are smaller and right values are larger under the usual rule
Sorted traversal Not guaranteed Inorder traversal produces sorted order for a standard BST

Types of Binary Trees

Full Binary Tree

A full binary tree is a binary tree where every node has either zero children or exactly two children. No node has exactly one child. 

        A
       / \
      B   C
     / \ / \
    D  E F  G

Complete Binary Tree

A complete binary tree has every level completely filled except possibly the last level. Nodes on the last level are placed from left to right without gaps. 

        A
       / \
      B   C
     / \ /
    D  E F

Perfect Binary Tree

A perfect binary tree has every internal node with exactly two children, and all leaf nodes are at the same level. 

        A
       / \
      B   C
     / \ / \
    D  E F  G

Skewed Binary Tree

A skewed binary tree is a tree where nodes are primarily arranged along one side. It can be left-skewed or right-skewed. 

Right-skewed:

A
 \
  B
   \
    C
     \
      D

Binary Tree Height

The height of a binary tree is commonly defined as the number of edges on the longest path from the root to a leaf. Under this definition, an empty tree has height -1 and a tree containing only the root has height 0. 

        A          depth 0
       / \
      B   C        depth 1
     /
    D              depth 2

Height = 2

Some implementations instead define height as the number of nodes on the longest path. When solving problems, always check which convention is being used.

Maximum Nodes at Each Level

In a binary tree, the maximum number of nodes at depth d is: 

Maximum nodes at depth d = 2^d

Therefore, the maximum number of nodes from depth 0 through depth h is: 

1 + 2 + 4 + ... + 2^h = 2^(h + 1) - 1

A perfect binary tree reaches this maximum at every level.

Minimum Height for n Nodes

Because each level of a binary tree can contain up to twice as many nodes as the previous level, a well-filled binary tree can store many nodes at a relatively small height.

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

Maximum nodes = 2^(h + 1) - 1

This relationship is important when analyzing the height of complete and balanced tree structures.

Binary Tree Node Implementation in JavaScript

A simple binary tree node can be represented using a class with three properties: the value, left child, and right child. 

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

Nodes can then be connected by assigning other nodes to the left and right properties. 

const root = new TreeNode(10);

root.left = new TreeNode(5);
root.right = new TreeNode(20);

root.left.left = new TreeNode(3);
root.left.right = new TreeNode(8);

Traversing a Binary Tree

Traversal means visiting every node in a particular order. Binary trees commonly use depth-first traversals and breadth-first traversal.

  • Preorder: Root → Left → Right
  • Inorder: Left → Root → Right
  • Postorder: Left → Right → Root
  • Level order: Visit nodes level by level
        10
       /  \
      5    20
     / \
    3   8

Preorder:   10, 5, 3, 8, 20
Inorder:     3, 5, 8, 10, 20
Postorder:   3, 8, 5, 20, 10
Level order: 10, 5, 20, 3, 8

Basic Binary Tree Operations

Common operations performed on binary trees include traversal, searching, insertion, deletion, finding height, counting nodes, and finding the minimum or maximum value. The exact behavior and complexity depend on whether the tree has additional structural rules, such as those found in a Binary Search Tree.

Operation Typical Complexity Reason
Traversal O(n) Every node is visited
Search O(n) worst case A general binary tree has no ordering rule
Height calculation O(n) Nodes may need to be examined
Count nodes O(n) Every node must be counted

Recursive Tree Processing

Binary trees naturally support recursive algorithms because every node can be viewed as the root of a smaller left subtree and a smaller right subtree. 

function countNodes(node) {
  if (node === null) {
    return 0;
  }

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

The base case handles an empty subtree. Otherwise, the current node contributes one to the result and the function recursively counts both child subtrees.

Applications of Binary Trees

Binary trees are useful as a foundation for several important data structures and algorithms.

  • Binary Search Trees for ordered data.
  • Heaps for priority-based processing.
  • Expression trees for representing mathematical expressions.
  • Decision trees for representing sequential choices.
  • Hierarchical data processing.
  • Tree-based searching and traversal algorithms.
  • Recursive problem-solving techniques.

Binary Tree vs Other Tree Structures

Structure Children Main Characteristic
General Tree Any number Hierarchical structure without a two-child limit
Binary Tree At most 2 Left and right child positions
Binary Search Tree At most 2 Maintains a value ordering property
Heap At most 2 Uses heap-order and commonly complete-tree structure

Common Mistakes

  • Assuming a binary tree must be sorted.
  • Confusing a binary tree with a Binary Search Tree.
  • Assuming every node must have exactly two children.
  • Confusing a complete binary tree with a full binary tree.
  • Assuming every binary tree is balanced.
  • Using binary-search logic on a general binary tree without an ordering guarantee.
  • Forgetting that left and right child positions are distinct.

Key Takeaways

  • A binary tree is a tree in which every node has at most two children.
  • The two child positions are called left and right.
  • A node can have zero, one, or two children.
  • A general binary tree does not require its values to be sorted.
  • Binary Search Trees are specialized binary trees with ordering rules.
  • Full, complete, perfect, and skewed describe different binary tree structures.
  • Binary tree traversal commonly uses preorder, inorder, postorder, and level order.
  • Binary trees are the foundation for structures such as BSTs and heaps.
  • Understanding binary tree structure makes recursive tree algorithms easier to design.

Code Examples 

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

const root = new TreeNode(10);

root.left = new TreeNode(5);
root.right = new TreeNode(20);

root.left.left = new TreeNode(3);
root.left.right = new TreeNode(8);

console.log(root);
    
function countNodes(node) {
  if (node === null) {
    return 0;
  }

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

console.log("Number of nodes:", countNodes(root));
    
function height(node) {
  if (node === null) {
    return -1;
  }

  return 1 + Math.max(
    height(node.left),
    height(node.right)
  );
}

console.log("Tree height:", height(root));
    
function inorder(node) {
  if (node === null) {
    return;
  }

  inorder(node.left);
  console.log(node.value);
  inorder(node.right);
}

inorder(root);

Pro Tip

Before applying a tree algorithm, identify what kind of binary tree you have. A general binary tree gives you only the two-child structure, while a BST, heap, or balanced tree provides additional properties that can make specific operations more efficient.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.