Step 1 of 6

17% Complete

Introduction to Binary Trees

Learn what binary trees are and why they're useful

What is a Binary Tree?

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Each node in a binary tree contains:

A data element (or value)
A reference to the left child
A reference to the right child

Types of Binary Trees

Full Binary Tree

A binary tree in which every node has either 0 or 2 children.

Complete Binary Tree

A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

Perfect Binary Tree

A binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level.

Binary Search Tree (BST)

A binary tree with the property that for each node, all elements in its left subtree are less than the node's value, and all elements in its right subtree are greater than the node's value.

Basic Structure of a Binary Tree Node

Here's how we define a basic binary tree node in TypeScript:

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

Why Use Binary Trees?

Binary trees are useful for many reasons:

Efficient Searching: Binary search trees provide O(log n) search time on average.
Hierarchical Structure: They naturally represent hierarchical relationships between data.
Efficient Insertions/Deletions: BSTs allow for efficient insertions and deletions.
Ordered Traversal: In-order traversal of a BST gives elements in sorted order.
Foundation for Advanced Data Structures: They form the basis for more complex structures like AVL trees, Red-Black trees, and heaps.

Common Operations

The main operations performed on binary trees include:

Insertion

Adding a new node to the tree

Deletion

Removing a node from the tree

Searching

Finding a specific value in the tree

Traversal

Visiting all nodes in the tree in a specific order (in-order, pre-order, post-order, level-order)

Next Steps

In the following sections, we'll explore each of these operations in detail, focusing on binary search trees (BSTs) as they are one of the most commonly used types of binary trees.