Binary Tree Traversals

Welcome to the world of Binary Tree Traversals! In this lesson, we'll explore the concept of binary trees and learn how to navigate through them using Ruby.

A binary tree is a powerful data structure where each node has up to two children—a left and a right child. Traversing a binary tree means visiting each node in a specific order, and Ruby’s intuitive syntax will make these traversal methods clear and approachable.

Before we dive into tree traversal methods, let’s first define the structure for a binary tree node. Each node will store a value and may have left and right children.

Here’s how to set up a basic TreeNode class:

class TreeNode
  attr_accessor :value, :left, :right

  def initialize(value = 0, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end

This TreeNode class creates a node with a given value and optional left and right children, which default to nil if not provided. This structure will be the foundation for the different tree traversal methods we’ll implement.

Binary trees are typically traversed in three primary ways: Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root). Let’s explore the Inorder traversal first, which recursively visits the left subtree, the root node, and finally, the right subtree. For a binary search tree, this sequence ensures that nodes are visited in ascending order.

Here’s an example of Inorder traversal in Ruby:

def inorder_traversal(root)
  return [] unless root

  inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)
end

# Test
root = TreeNode.new(1, nil, TreeNode.new(2, TreeNode.new(3)))
puts inorder_traversal(root).inspect  # Output: [1, 3, 2]

In this code, we first traverse the left subtree, then add the root node’s value, and finally traverse the right subtree. This recursive approach gives us a clear, ordered path through the tree.

Let's examine the algorithm a bit closer. The inorder_traversal method performs the following steps:

1. Base Case:

   return [] unless root

   If the current node (root) is nil, return an empty array. This stops the recursion when a leaf node's child is reached.

2. Recursive Traversal:

   inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)

   • Left Subtree: Recursively traverse the left child of the current node.
   • Root Node: Add the current node's value to the result array.
   • Right Subtree: Recursively traverse the right child of the current node.

   The results from the left subtree, the root node, and the right subtree are concatenated to form the final traversal order.

3. Testing the Function:

   root = TreeNode.new(1, nil, TreeNode.new(2, TreeNode.new(3)))
   puts inorder_traversal(root).inspect  # Output: [1, 3, 2]

   This creates a binary tree and prints the result of the inorder traversal, which should output [1, 3, 2].