Back to Main ACS 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 (Java)
class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Tree Traversal Methods (Java)
public static List<Integer> preOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preOrderHelper(root, result);
    return result;
}
private static void preOrderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.value); // Visit node
    preOrderHelper(node.left, result);
    preOrderHelper(node.right, result);
}

public static List<Integer> inOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inOrderHelper(root, result);
    return result;
}
private static void inOrderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inOrderHelper(node.left, result);
    result.add(node.value); // Visit node
    inOrderHelper(node.right, result);
}

public static List<Integer> postOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postOrderHelper(root, result);
    return result;
}
private static void postOrderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postOrderHelper(node.left, result);
    postOrderHelper(node.right, result);
    result.add(node.value); // Visit node
}

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 Insert

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.

// Binary Search Tree (Java)
class BinarySearchTree {
    TreeNode root;
    public BinarySearchTree() {
        this.root = null;
    }
    // Insert a value into the BST
    public void insert(int value) {
        root = insertRec(root, value);
    }
    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) return new TreeNode(value);
        if (value < root.value) root.left = insertRec(root.left, value);
        else if (value > root.value) root.right = insertRec(root.right, value);
        return root;
    }
    // Search for a value in the BST
    public boolean search(int value) {
        return searchRec(root, value) != null;
    }
    private TreeNode searchRec(TreeNode root, int value) {
        if (root == null || root.value == value) return root;
        if (value < root.value) return searchRec(root.left, value);
        return searchRec(root.right, value);
    }
}

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

// Binary Tree Node (Java)
class BinaryTreeNode {
    int value;
    BinaryTreeNode left, right;
    BinaryTreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

This basic implementation includes:

Value storage
Left child reference
Right child reference

Tree Traversal Methods

// In-order Traversal (Java)
public static void inOrderTraversal(BinaryTreeNode node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.println(node.value);
        inOrderTraversal(node.right);
    }
}

// Pre-order Traversal (Java)
public static void preOrderTraversal(BinaryTreeNode node) {
    if (node != null) {
        System.out.println(node.value);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

// Post-order Traversal (Java)
public static void postOrderTraversal(BinaryTreeNode node) {
    if (node != null) {
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.println(node.value);
    }
}

Binary Search Tree Operations

// Insert into BST (Java)
public static BinaryTreeNode insert(BinaryTreeNode root, int value) {
    if (root == null) return new BinaryTreeNode(value);
    if (value < root.value) root.left = insert(root.left, value);
    else root.right = insert(root.right, value);
    return root;
}

// Search in BST (Java)
public static BinaryTreeNode search(BinaryTreeNode root, int value) {
    if (root == null || 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.