Day 14

Day 14: Binary Trees

Intermediate 14 min

14/60 Days

Binary Trees#

Welcome to Day 14 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deep into Binary Trees, a fundamental data structure in computer science and a specific type of tree we introduced yesterday.

What is a Binary Tree?#

A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. This restriction on the number of children makes binary trees particularly useful in various applications and algorithms.

Properties of Binary Trees#

The maximum number of nodes at level ’l’ of a binary tree is 2^l.
The maximum number of nodes in a binary tree of height ‘h’ is 2^(h+1) - 1.
In a binary tree with N nodes, the minimum possible height or the minimum number of levels is log2(N+1) - 1.
A binary tree with L leaves has at least log2(L) + 1 levels.

Types of Binary Trees#

Full Binary Tree: Every node has 0 or 2 children.
Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level.
Balanced Binary Tree: The …

Binary Trees#

What is a Binary Tree?#

Properties of Binary Trees#

The maximum number of nodes at level ’l’ of a binary tree is 2^l.
The maximum number of nodes in a binary tree of height ‘h’ is 2^(h+1) - 1.
In a binary tree with N nodes, the minimum possible height or the minimum number of levels is log2(N+1) - 1.
A binary tree with L leaves has at least log2(L) + 1 levels.

Types of Binary Trees#

Full Binary Tree: Every node has 0 or 2 children.
Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level.
Balanced Binary Tree: The height of the left and right subtrees of every node differs by at most one.
Degenerate (or Pathological) Tree: Every internal node has only one child.

Implementing a Binary Tree in Python#

Let’s implement a basic Binary Tree structure:

 1class BinaryTreeNode:
 2    def __init__(self, value):
 3        self.value = value
 4        self.left = None
 5        self.right = None
 6
 7class BinaryTree:
 8    def __init__(self, root_value):
 9        self.root = BinaryTreeNode(root_value)
10
11    def insert_left(self, node, value):
12        if node is None:
13            return BinaryTreeNode(value)
14        node.left = self.insert_left(node.left, value)
15        return node
16
17    def insert_right(self, node, value):
18        if node is None:
19            return BinaryTreeNode(value)
20        node.right = self.insert_right(node.right, value)
21        return node
22
23    def print_tree(self, node, level=0):
24        if node is not None:
25            self.print_tree(node.right, level + 1)
26            print(' ' * 4 * level + '->', node.value)
27            self.print_tree(node.left, level + 1)
28
29# Example usage
30tree = BinaryTree(1)
31tree.root.left = BinaryTreeNode(2)
32tree.root.right = BinaryTreeNode(3)
33tree.root.left.left = BinaryTreeNode(4)
34tree.root.left.right = BinaryTreeNode(5)
35
36print("Binary Tree Structure:")
37tree.print_tree(tree.root)

Binary Tree Traversals#

There are three main types of depth-first traversals for binary trees:

Inorder Traversal (Left, Root, Right)
Preorder Traversal (Root, Left, Right)
Postorder Traversal (Left, Right, Root)

Let’s implement these traversals:

 1class BinaryTree:
 2    # ... (previous methods remain the same)
 3
 4    def inorder_traversal(self, node):
 5        if node:
 6            self.inorder_traversal(node.left)
 7            print(node.value, end=' ')
 8            self.inorder_traversal(node.right)
 9
10    def preorder_traversal(self, node):
11        if node:
12            print(node.value, end=' ')
13            self.preorder_traversal(node.left)
14            self.preorder_traversal(node.right)
15
16    def postorder_traversal(self, node):
17        if node:
18            self.postorder_traversal(node.left)
19            self.postorder_traversal(node.right)
20            print(node.value, end=' ')
21
22# Example usage
23tree = BinaryTree(1)
24tree.root.left = BinaryTreeNode(2)
25tree.root.right = BinaryTreeNode(3)
26tree.root.left.left = BinaryTreeNode(4)
27tree.root.left.right = BinaryTreeNode(5)
28
29print("Inorder Traversal:")
30tree.inorder_traversal(tree.root)
31print("\nPreorder Traversal:")
32tree.preorder_traversal(tree.root)
33print("\nPostorder Traversal:")
34tree.postorder_traversal(tree.root)

Level Order Traversal (Breadth-First Search)#

We can also perform a level order traversal, which visits nodes level by level from left to right:

 1from collections import deque
 2
 3class BinaryTree:
 4    # ... (previous methods remain the same)
 5
 6    def level_order_traversal(self):
 7        if not self.root:
 8            return
 9        
10        queue = deque([self.root])
11        while queue:
12            level_size = len(queue)
13            for _ in range(level_size):
14                node = queue.popleft()
15                print(node.value, end=' ')
16                if node.left:
17                    queue.append(node.left)
18                if node.right:
19                    queue.append(node.right)
20            print()  # New line for each level
21
22# Example usage
23tree = BinaryTree(1)
24tree.root.left = BinaryTreeNode(2)
25tree.root.right = BinaryTreeNode(3)
26tree.root.left.left = BinaryTreeNode(4)
27tree.root.left.right = BinaryTreeNode(5)
28
29print("Level Order Traversal:")
30tree.level_order_traversal()

Common Binary Tree Operations#

Finding the Height of a Binary Tree:

1def height(node):
2    if not node:
3        return 0
4    left_height = height(node.left)
5    right_height = height(node.right)
6    return max(left_height, right_height) + 1

Counting Nodes in a Binary Tree:

1def count_nodes(node):
2    if not node:
3        return 0
4    return 1 + count_nodes(node.left) + count_nodes(node.right)

Checking if a Binary Tree is Balanced:

 1def is_balanced(node):
 2    def check_balance(node):
 3        if not node:
 4            return 0
 5        left = check_balance(node.left)
 6        right = check_balance(node.right)
 7        if left == -1 or right == -1 or abs(left - right) > 1:
 8            return -1
 9        return max(left, right) + 1
10
11    return check_balance(node) != -1

Applications of Binary Trees#

Expression Trees: For representing and evaluating arithmetic expressions.
Huffman Coding Trees: Used in data compression algorithms.
Binary Search Trees: For efficient searching and sorting.
Priority Queues: Heap is a binary tree-based data structure used in priority queues.
Syntax Trees: In compilers to represent the structure of program code.

Time Complexity#

For a balanced binary tree:

Insertion: O(log n)
Deletion: O(log n)
Search: O(log n)

For an unbalanced binary tree, these operations can degrade to O(n) in the worst case.

Exercise#

Implement a function to find the lowest common ancestor of two nodes in a binary tree.
Create a method to check if a binary tree is a full binary tree.
Implement a function to find the diameter of a binary tree (the longest path between any two nodes).

Summary#

Today, we explored Binary Trees in depth, including their properties, types, implementations, and common operations. Binary Trees are fundamental to many advanced data structures and algorithms, and understanding them thoroughly is crucial for solving complex problems efficiently.

Binary Trees form the basis for more specialized tree structures like Binary Search Trees and Heaps, which we’ll explore in the coming days. The traversal techniques and operations we’ve learned today will be invaluable as we delve deeper into tree-based data structures and algorithms.

Tomorrow, we’ll focus on Binary Search Trees, a special type of binary tree that maintains a specific ordering of nodes for efficient searching and sorting operations. Stay tuned!

Solution#

The worked solution is a lifetime-access perk. Unlock all 60 solutions. Already purchased? Log in to view it.

Show the solution

These functions operate on BinaryTreeNode objects, each with left and right children.

 1def lowest_common_ancestor(root, a, b):
 2    if root is None or root.value in (a, b):
 3        return root
 4    left = lowest_common_ancestor(root.left, a, b)
 5    right = lowest_common_ancestor(root.right, a, b)
 6    if left and right:
 7        return root          # a and b are in different subtrees
 8    return left or right
 9
10
11def is_full_binary_tree(node):
12    if node is None:
13        return True
14    if (node.left is None) != (node.right is None):
15        return False         # exactly one child means not full
16    return is_full_binary_tree(node.left) and is_full_binary_tree(node.right)
17
18
19def diameter(node):
20    best = 0
21
22    def depth(n):
23        nonlocal best
24        if n is None:
25            return 0
26        left = depth(n.left)
27        right = depth(n.right)
28        best = max(best, left + right)   # edges passing through n
29        return 1 + max(left, right)
30
31    depth(node)
32    return best

lowest_common_ancestor returns the node where the two targets first split into different subtrees. is_full_binary_tree verifies every node has zero or two children. diameter tracks the longest path (in edges) through any node while computing depths in a single traversal. All three visit each node once for O(n) time, using O(h) space for the recursion stack, where h is the tree height.

Keep your momentum going

Create a free account to unlock the full lesson, all 60 days, and track your progress as you go.