Back to Welcome Page

Binary Trees I

Learn the fundamentals of binary trees, their properties, and basic operations. Master the essential concepts that form the foundation of tree data structures.

Learning Objectives

Core Concepts

Understanding binary tree structure
Tree traversal methods
Binary search tree properties
Basic tree operations

Skills Development

Implementing tree nodes
Tree manipulation algorithms
Recursive problem-solving
Tree visualization techniques

Prerequisites

Required Knowledge

Basic Python programming
Understanding of classes and objects
Familiarity with recursion
Basic data structures concepts

Recommended Preparation

Review linked list concepts
Practice recursive functions
Understand time complexity
Study Python class inheritance

1. Introduction to Binary Trees

Key Topics

Tree terminology and concepts
Binary tree structure
Applications of binary trees
Tree traversal introduction

Understanding Binary Trees

A binary tree is a hierarchical data structure consisting of nodes, where each node has at most two children (left and right). Binary trees are used in various applications from expressing hierarchical relationships to implementing efficient searching and sorting algorithms.

Important Terminology:

Root: The topmost node in the tree
Parent: A node that has child nodes
Child: A node that has a parent node
Leaf: A node with no children
Subtree: A tree consisting of a node and all its descendants
Depth: The number of edges from the root to a particular node
Height: The number of edges on the longest path from a node to a leaf

Types of Binary Trees:

Full Binary Tree: Every node has 0 or 2 children
Complete Binary Tree: All levels are filled except possibly the last, which is filled from left to right
Perfect Binary Tree: All internal nodes have 2 children and all leaves are at the same level
Balanced Binary Tree: The height difference between left and right subtrees is not more than 1 for all nodes
Binary Search Tree (BST): For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater

2. Tree Traversal

Key Topics

Depth-first traversal methods
Pre-order traversal
In-order traversal
Post-order traversal

Tree Traversal Methods

Tree traversal is the process of visiting each node in a tree data structure exactly once. There are several ways to traverse a binary tree:

Depth-First Traversals:

Pre-order (Root, Left, Right):
- Visit the current node
- Recursively traverse the left subtree
- Recursively traverse the right subtree
In-order (Left, Root, Right):
- Recursively traverse the left subtree
- Visit the current node
- Recursively traverse the right subtree
Post-order (Left, Right, Root):
- Recursively traverse the left subtree
- Recursively traverse the right subtree
- Visit the current node

// Binary Tree Node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Tree Traversal Methods
function preOrderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    // Root, Left, Right
    result.push(node.value);  // Visit node
    traverse(node.left);      // Traverse left subtree
    traverse(node.right);     // Traverse right subtree
  }
  
  traverse(root);
  return result;
}

function inOrderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    // Left, Root, Right
    traverse(node.left);      // Traverse left subtree
    result.push(node.value);  // Visit node
    traverse(node.right);     // Traverse right subtree
  }
  
  traverse(root);
  return result;
}

function postOrderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    // Left, Right, Root
    traverse(node.left);      // Traverse left subtree
    traverse(node.right);     // Traverse right subtree
    result.push(node.value);  // Visit node
  }
  
  traverse(root);
  return result;
}

Applications of Different Traversals:

Pre-order: Used to create a copy of the tree or prefix expression (Polish notation)
In-order: In BST, gives nodes in non-decreasing order
Post-order: Used to delete the tree or postfix expression (Reverse Polish notation)

Practice: Binary Tree Preorder Traversal on LeetCode →

3. Binary Search Trees

Key Topics

Binary search tree properties
Insertion and search operations
Time and space complexity
BST applications

Binary Search Trees (BST)

A Binary Search Tree is a special type of binary tree with the following properties:

All nodes in the left subtree have values less than the node's value
All nodes in the right subtree have values greater than the node's value
Both the left and right subtrees are also BSTs

The BST property allows for efficient searching, insertion, and deletion operations with an average time complexity of O(log n) for a balanced tree.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // Insert a value into the BST
  insert(value) {
    const newNode = new TreeNode(value);
    
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    
    let current = this.root;
    
    while (true) {
      // Handle duplicate values (optional)
      if (value === current.value) return this;
      
      // Go left if value is less than current
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } 
      // Go right if value is greater than current
      else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }
  
  // Search for a value in the BST
  search(value) {
    if (this.root === null) return false;
    
    let current = this.root;
    
    while (current) {
      if (value === current.value) return true;
      
      // Decide whether to go left or right
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    
    return false; // Value not found
  }
}

BST Operations Complexity:

Search: Average O(log n), Worst O(n) when unbalanced
Insert: Average O(log n), Worst O(n) when unbalanced
Delete: Average O(log n), Worst O(n) when unbalanced

Applications of BST:

Implementing map, set, and multiset data structures
Priority queues
Searching and sorting algorithms
Database indexing

Practice: Validate Binary Search Tree on LeetCode →

Code Implementation

Binary Tree Node Class

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

This basic implementation includes:

Value storage
Left child reference
Right child reference

Tree Traversal Methods

def in_order_traversal(node):
    if node:
        in_order_traversal(node.left)
        print(node.value)
        in_order_traversal(node.right)

def pre_order_traversal(node):
    if node:
        print(node.value)
        pre_order_traversal(node.left)
        pre_order_traversal(node.right)

def post_order_traversal(node):
    if node:
        post_order_traversal(node.left)
        post_order_traversal(node.right)
        print(node.value)

Binary Search Tree Operations

def insert(root, value):
    if root is None:
        return BinaryTreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def search(root, value):
    if root is None or root.value == value:
        return root
    if value < root.value:
        return search(root.left, value)
    return search(root.right, value)

Practice Problems

1. Tree Height Calculation

Write a function to calculate the height of a binary tree.

Example:

Input:
     1
    / \
   2   3
  / \
 4   5

Output: 3

2. Level Order Traversal

Implement level-order traversal using a queue.

Example:

Input:
     1
    / \
   2   3
  / \
 4   5

Output: [1, 2, 3, 4, 5]

3. Check if Binary Tree is Balanced

Implement a function to check if a binary tree is balanced (the height difference between left and right subtrees is not more than 1 for all nodes).

Example:

Balanced Tree:
     1
    / \
   2   3
  / \
 4   5

Not Balanced:
     1
    / 
   2   
  / 
 3  
/
4

LeetCode Binary Tree Problems

Practice with these recommended LeetCode problems to strengthen your binary tree skills:

Beginner Problems

Intermediate Problems

Note: Previously, this course referenced the CodeSignal Arcade, which is no longer available. The LeetCode problems above follow the same principles and are an excellent alternative for practicing binary tree algorithms and preparing for technical interviews.