Algorithms 101: Understanding Recursive Tree Operations

The Nature of Trees: Recursive Data Structures

Trees are inherently recursive data structures. A tree is made of sub-trees, which in turn are made of other sub-trees, and ultimately, all these sub-trees form the same tree. Each node in a tree can be considered a tree itself because you can traverse the entire tree starting from any single node. This is why trees are often perceived as recursive data structures.

Understanding Recursive Tree Operations

Example: In-Order Traversal

Let’s understand how to implement an in-order traversal of a tree using recursion. In-order traversal involves visiting the right child, then the node itself, and finally the left child.

Python Example

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

def in_order_traversal(node):
    if node is None:
        return
    in_order_traversal(node.right)
    print(node.value, end=" ")
    in_order_traversal(node.left)

# Creating a sample tree: 1 <- 2 -> 3
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

# In-order traversal
in_order_traversal(root)  # Output: 3 2 1

JavaScript Example

class TreeNode {
    constructor(value = 0, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function inOrderTraversal(node) {
    if (node === null) {
        return;
    }
    inOrderTraversal(node.right);
    console.log(node.value);
    inOrderTraversal(node.left);
}

// Creating a sample tree: 1 <- 2 -> 3
const root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);

// In-order traversal
inOrderTraversal(root);  // Output: 3 2 1

Explanation with Call Stack

For the tree 1 <- 2 -> 3, the call stack evolves as follows during in-order traversal:

1. in_order_traversal(2) is called.
   • Stack: [in_order_traversal(2)]
2. in_order_traversal(3) is called.
   • Stack: [in_order_traversal(2), in_order_traversal(3)]
3. Base case in_order_traversal(null) returns.
   • Stack: [in_order_traversal(2), in_order_traversal(3)]
4. Print 3.
   • Stack: [in_order_traversal(2)]
5. in_order_traversal(1) is called.
   • Stack: [in_order_traversal(2), in_order_traversal(1)]
6. Base case in_order_traversal(null) returns.
   • Stack: [in_order_traversal(2), in_order_traversal(1)]
7. Print 1.
   • Stack: [in_order_traversal(2)]
8. Print 2.
   • Stack: []

Each recursive call adds a new frame to the stack, and these frames are popped off as the traversal is completed.

Recursive Logic in Trees

Expanding the Concept

To traverse a tree, we start with one node, the root node, and solve the problem specifically for this node. Then, we expand the solution to include its children, making the traversal method scalable. This approach is common in tree operations like insertion, deletion, and traversal.

Example: Inserting a Node

Let’s consider inserting a node into a binary search tree (BST).

Python Example

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

# Insert nodes into the BST
root = TreeNode(2)
insert(root, 1)
insert(root, 3)

# In-order traversal to check the insertion
in_order_traversal(root)  # Output: 3 2 1

JavaScript Example

function insert(node, value) {
    if (node === null) {
        return new TreeNode(value);
    }
    if (value < node.value) {
        node.left = insert(node.left, value);
    } else {
        node.right = insert(node.right, value);
    }
    return node;
}

// Insert nodes into the BST
const root = new TreeNode(2);
insert(root, 1);
insert(root, 3);

// In-order traversal to check the insertion
inOrderTraversal(root);  // Output: 3 2 1

Explanation with Call Stack

For inserting 1 and 3 into the BST with root 2, the call stack evolves as follows:

1. insert(2, 1) is called.
   • Stack: [insert(2, 1)]
2. insert(null, 1) is called.
   • Stack: [insert(2, 1), insert(null, 1)]
3. Base case returns a new node 1.
   • Stack: [insert(2, 1)]
4. insert(2, 3) is called.
   • Stack: [insert(2, 3)]
5. insert(null, 3) is called.
   • Stack: [insert(2, 3), insert(null, 3)]
6. Base case returns a new node 3.
   • Stack: [insert(2, 3)]
7. Root 2 now has left child 1 and right child 3.

Avoiding Stack Overflow

Every recursive method must have a base case to avoid stack overflow exceptions. In the case of tree operations, the base case is often when a null node is reached, indicating the end of a branch.

Summary

Recursion is a powerful tool for tree operations, allowing you to handle complex data structures with ease. By understanding the call stack and how recursive functions operate, you can efficiently implement tree operations like traversal.

Recommend Resources:

Understanding Recursion With Trees | Trees and Recursion | Recursive Data Structures | Geekific