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
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Tree Traversal Methods
def pre_order_traversal(root):
    result = []
    
    def traverse(node):
        if node is None:
            return
        
        # Root, Left, Right
        result.append(node.value)  # Visit node
        traverse(node.left)        # Traverse left subtree
        traverse(node.right)       # Traverse right subtree
    
    traverse(root)
    return result

def in_order_traversal(root):
    result = []
    
    def traverse(node):
        if node is None:
            return
        
        # Left, Root, Right
        traverse(node.left)        # Traverse left subtree
        result.append(node.value)  # Visit node
        traverse(node.right)       # Traverse right subtree
    
    traverse(root)
    return result

def post_order_traversal(root):
    result = []
    
    def traverse(node):
        if node is None:
            return
        
        # Left, Right, Root
        traverse(node.left)        # Traverse left subtree
        traverse(node.right)       # Traverse right subtree
        result.append(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 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.

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    # Insert a value into the BST
    def insert(self, value):
        new_node = TreeNode(value)
        
        if self.root is None:
            self.root = new_node
            return self
        
        current = self.root
        
        while True:
            # Handle duplicate values (optional)
            if value == current.value:
                return self
            
            # Go left if value is less than current
            if value < current.value:
                if current.left is None:
                    current.left = new_node
                    return self
                current = current.left
            # Go right if value is greater than current
            else:
                if current.right is None:
                    current.right = new_node
                    return self
                current = current.right
    
    # Search for a value in the BST
    def search(self, value):
        if self.root is None:
            return False
        
        current = self.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.