LearnDSA.me - Master Data Structures & Algorithms

A binary tree is a tree data structure where each node has at most two children, typically referred to as the left child and right child. This simple constraint makes binary trees incredibly versatile and efficient for many operations.

Binary Tree Properties:

Each node has at most 2 children

Children are distinguished as "left" and "right"

Maximum nodes at level i: 2^i

Height h tree has at most 2^(h+1) - 1 nodes

Types of Binary Trees:

Full Binary Tree: Every node has 0 or 2 children

Complete Binary Tree: All levels filled except possibly last (left-filled)

Perfect Binary Tree: All internal nodes have 2 children, leaves at same level

Balanced Binary Tree: Height difference between subtrees ≤ 1

Binary Tree Structure

Root: 50 (top level)

Internal Nodes: 50, 30, 70 (have children)

Leaves: 20, 40, 80 (no children)

Height: 2 (maximum edges from root to leaf)

Size: 6 nodes total

Binary Search Trees (BST)

A Binary Search Tree is a binary tree with a special ordering property: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger than the node's value.

BST Property:

Left Subtree: All values < node value

Right Subtree: All values > node value

In-order Traversal: Produces sorted sequence

BST Advantages:

Efficient search: O(log n) average case

Dynamic size: Can grow/shrink during runtime

Ordered data: In-order traversal gives sorted output

Range queries: Easy to find values in a range

BST Example

In-order: 8, 10, 12, 15, 17, 20, 25 (sorted!)

Search path for 17: 15 → 20 → 17 (3 steps)

All left subtree values < parent

All right subtree values > parent

BST Operations

Insert Algorithm:

1Start at root node
2Compare new value with current node
3Go left if smaller, right if larger
4When you reach null, insert new node there

Time Complexity:

O(log n) average, O(n) worst case

Implementation:

JavaScript

function insert(root, value) {
  if (!root) return new Node(value);
  
  if (value < root.val) {
    root.left = insert(root.left, value);
  } else if (value > root.val) {
    root.right = insert(root.right, value);
  }
  
  return root;
}

Tree Balancing & Performance

The performance of BST operations depends heavily on the tree's balance. An unbalanced tree can degrade to O(n) performance, essentially becoming a linked list.

The Balancing Problem:

Worst Case: Inserting sorted data creates a skewed tree

Example: Insert [1, 2, 3, 4, 5] sequentially

Result: Linear chain (essentially a linked list)

Performance: O(n) instead of O(log n)

Self-Balancing Trees:

AVL Trees: Height-balanced, rotations on insert/delete

Red-Black Trees: Color-based balancing rules

Splay Trees: Recently accessed nodes move to root

Balanced vs Unbalanced

Balanced Tree

Height: 2, Search: O(log n)

Unbalanced Tree

Height: 3, Search: O(n)

Performance Comparison:

Tree Type	Search	Insert	Delete
Balanced BST	O(log n)	O(log n)	O(log n)
Unbalanced BST	O(n)	O(n)	O(n)
AVL Tree	O(log n)	O(log n)	O(log n)

Previous: Tree Basics Next: Tree Traversal

function insert(root, value) { if (!root) return new Node(value); if (value < root.val) { root.left = insert(root.left, value); } else if (value > root.val) { root.right = insert(root.right, value); } return root; }

Tree Type

Insert

Delete

Balanced BST

O(log n)

Unbalanced BST

O(n)

AVL Tree

O(log n)