Binary Trees

A binary tree is a hierarchical data structure in which every node has at most two children, commonly called:

• Left child
• Right child

It is a special form of a tree data structure (a non-linear structure used to represent hierarchical relationships).

Learn JavaScript from the comfort of your home

        (Root)
         /  \
     Left   Right

Core Terminology

✔ Node

The basic storage unit. It contains:

• A value/data
• A reference to left child
• A reference to right child

✔ Root

The topmost node in the tree.

✔ Leaf

A node with no children.

✔ Parent

A node with at least one child.

✔ Child

A node connected below another.

✔ Subtree

A tree within the main tree.

✔ Height of a node

Length of the longest downward path to a leaf.

✔ Depth of a node

Distance from the root to that node.

Characteristics of Binary Trees

1. Each node has ≤ 2 children
2. The tree is recursive by nature
   (each child can itself be treated as a tree)
3. They can be:
   • Complete
   • Full
   • Perfect
   • Balanced
   • Degenerate (like a linked list)

Understanding these variations is important.

Apply to learn software engineering at Codeflare’s Academy

Types of Binary Trees

1. Full Binary Tree

Every node has 0 or 2 children.

        A
       / \
      B   C

2. Complete Binary Tree

All levels are filled except possibly the last, and nodes are as far left as possible.

3. Perfect Binary Tree

All interior nodes have 2 children and all leaves are at the same level.

4. Balanced Binary Tree

For every node, the height of left and right subtrees differ by at most 1.
(Used for fast searching — e.g., AVL, Red-Black trees)

5. Degenerate Tree

Every parent has only one child, making it behave like a linked list.

Binary Tree vs Binary Search Tree (BST)

A Binary Tree is a general structure.

A Binary Search Tree (BST) is a special binary tree with the rule:

Left subtree values < Node value < Right subtree values

This property enables fast search, insertion, deletion (O(log n) average).

Tree Traversal Methods

To access all nodes, you traverse the tree. There are two main categories:

Depth-First Search (DFS) Traversals

1. In-order Traversal (Left → Root → Right)

• Main use: retrieves sorted data from BST.

2. Pre-order Traversal (Root → Left → Right)

• Main use: create a copy of the tree, serialize it.

3. Post-order Traversal (Left → Right → Root)

• Main use: delete the tree, evaluate expressions.

Example Tree:

        1
       / \
      2   3

Traversals:

• In-order → 2, 1, 3
• Pre-order → 1, 2, 3
• Post-order → 2, 3, 1

Breadth-First Search (BFS)

Level-order Traversal

Visit nodes level by level.

Level order → 1, 2, 3, 4, 5...

Uses a queue internally.

Operations on Binary Trees

✔ Insertion

Depends on tree type
(e.g., BST inserts smaller values left, larger right).

✔ Deletion

More complex — especially if the node has 2 children.

✔ Searching

DFS or BFS.

✔ Height / Depth Calculations

Used in balancing algorithms.

Binary Tree Implementation (Simplified)

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

class BinaryTree {
    constructor(rootValue) {
        this.root = new Node(rootValue);
    }

    // Pre-order traversal (Root → Left → Right)
    preorder(node) {
        if (node !== null) {
            console.log(node.value);
            this.preorder(node.left);
            this.preorder(node.right);
        }
    }
}

Example Usage

const tree = new BinaryTree(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);

tree.preorder(tree.root); 
// Output: 1, 2, 3

Applications of Binary Trees

✔ Binary Search Trees (BSTs)

Fast searching, inserting, deleting.

✔ Heaps

Used for priority queues, implemented as complete binary trees.

✔ Syntax Trees / Expression Trees

Used in compilers and interpreters.

✔ Routing Tables, File Systems, AI (decision trees)

✔ Huffman Coding Trees

For file compression algorithms.

Why Binary Trees Matter

They provide:

• Efficient data storage
• Fast lookups
• Hierarchical representation
• Foundation for advanced structures
  (BST, AVL, Red-Black Trees, Heaps, Tries)

Binary trees are one of the most fundamental data structures in computer science — understanding them makes advanced algorithms much easier.