Ilustrated Guide for Binary Tree in Golang

Binary Tree is one of the most fundamental data structures in computer science. In this guide, we'll explore how to implement a Binary Tree in Go, with detailed step-by-step diagrams that visualize each operation.

What is a Binary Tree?

A Binary Tree is a hierarchical data structure where each node has at most two children, typically referred to as the left child and right child. Unlike a Binary Search Tree (BST), a Binary Tree doesn't enforce any ordering rules on the values stored in nodes.

Key Terminology

Before we dive into implementation, let's understand the basic terms:

• Root: The topmost node in the tree. It has no parent.
• Node: An element that stores data and references to its children.
• Leaf: A node that has no children (both left and right are nil).
• Parent: A node that has one or more children.
• Child: A node directly connected to another node when moving away from the root.
• Left Child: The child node on the left side of a parent.
• Right Child: The child node on the right side of a parent.
• Subtree: A tree formed by a node and all its descendants.

Basic Structure

Here's a visual representation of a Binary Tree:

In this example:

• Node 10 is the root
• Nodes 5 and 15 are children of the root
• Nodes 3, 7, 12, and 20 are leaf nodes (they have no children)
• Node 3, 5, and 12 are left children of their parent
• Node 7, 15, and 20 are right children of their parent

Node Structure and Basic Setup

Let's start by defining the basic structure for our Binary Tree in Go.

Node Structure

Each node in our Binary Tree will store a value and pointers to its left and right children:

// Node represents a node in the Binary Tree
type Node struct {
    Value int
    Left  *Node
    Right *Node
}

Binary Tree Structure

The Binary Tree itself only needs to hold a reference to the root node:

// BinaryTree represents a Binary Tree
type BinaryTree struct {
    Root *Node
}

Constructor

We'll create a constructor function to initialize a new empty Binary Tree:

// NewBinaryTree creates a new empty Binary Tree
func NewBinaryTree() *BinaryTree {
    return &BinaryTree{Root: nil}
}

Initially, the tree is empty, so the root is nil. Let's visualize this:

Insert Operation

Inserting nodes into a Binary Tree requires a strategy. For simplicity, we'll use a level-order insertion approach: we insert nodes from left to right at each level, filling each level completely before moving to the next.

Important Note: This insertion strategy always creates a Complete Binary Tree (CBT) - a tree where all levels are completely filled except possibly the last level, which is filled from left to right. This property ensures the tree maintains a balanced structure and allows for efficient array-based representation.

Insert Implementation

Here's the implementation using a queue-based approach:

// Insert adds a new node to the tree using level-order insertion
func (bt *BinaryTree) Insert(value int) {
    newNode := &Node{Value: value}

    // If tree is empty, make this node the root
    if bt.Root == nil {
        bt.Root = newNode
        return
    }

    // Use a queue to find the first available position
    queue := []*Node{bt.Root}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        // If left child is empty, insert here
        if node.Left == nil {
            node.Left = newNode
            return
        }

        // If right child is empty, insert here
        if node.Right == nil {
            node.Right = newNode
            return
        }

        // Both children exist, add them to queue for next level
        queue = append(queue, node.Left, node.Right)
    }
}

Step-by-Step Insertion

Let's visualize the insertion process step by step. We'll insert values: 10, 5, 15, 3, 7, 12, 20.

Delete Operation

Deleting a node from a Binary Tree that uses level-order insertion requires a specific approach to maintain the Complete Binary Tree (CBT) property. Since we're maintaining a CBT structure, we need to:

1. Find the node to delete
2. Find the deepest, rightmost node (the last node in level-order traversal)
3. Replace the deleted node's value with the rightmost node's value
4. Delete the rightmost node from the last level

This approach ensures the tree remains a Complete Binary Tree after deletion, maintaining the level-order structure.

Delete Implementation

// Delete removes a node with the given value from the tree
// It maintains the Complete Binary Tree property by replacing
// the deleted node with the rightmost node in the last level
func (bt *BinaryTree) Delete(value int) bool {
    if bt.Root == nil {
        return false
    }

    // Find the node to delete and its parent
    var nodeToDelete *Node
    var parent *Node
    var isLeftChild bool

    // Special case: deleting the root
    if bt.Root.Value == value {
        nodeToDelete = bt.Root
    } else {
        // Find the node using level-order traversal
        queue := []*Node{bt.Root}

        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]

            if node.Left != nil {
                if node.Left.Value == value {
                    parent = node
                    nodeToDelete = node.Left
                    isLeftChild = true
                    break
                }
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                if node.Right.Value == value {
                    parent = node
                    nodeToDelete = node.Right
                    isLeftChild = false
                    break
                }
                queue = append(queue, node.Right)
            }
        }
    }

    if nodeToDelete == nil {
        return false // Value not found
    }

    // Find the rightmost node in the last level
    rightmostNode, rightmostParent := bt.findRightmostNode()

    if rightmostNode == nil {
        // Tree has only one node (root)
        bt.Root = nil
        return true
    }

    // Replace the value of the node to delete with the rightmost node's value
    nodeToDelete.Value = rightmostNode.Value

    // Delete the rightmost node
    if rightmostParent != nil {
        if rightmostParent.Right == rightmostNode {
            rightmostParent.Right = nil
        } else {
            rightmostParent.Left = nil
        }
    } else {
        // Rightmost node is the root (tree has only root)
        bt.Root = nil
    }

    return true
}

// findRightmostNode finds the rightmost node in the last level.
// Returns the node and its parent
func (bt *BinaryTree) findRightmostNode() (*Node, *Node) {
    if bt.Root == nil {
        return nil, nil
    }

    if bt.Root.Left == nil && bt.Root.Right == nil {
        // Only root exists
        return bt.Root, nil
    }

    queue := []*Node{bt.Root}
    var rightmostNode *Node
    var rightmostParent *Node

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        // Track the rightmost node at the current level
        if node.Left != nil {
            rightmostNode = node.Left
            rightmostParent = node
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            rightmostNode = node.Right
            rightmostParent = node
            queue = append(queue, node.Right)
        }
    }

    return rightmostNode, rightmostParent
}

Delete Operation Steps

The deletion process for a Complete Binary Tree follows these steps:

1. Find the node to delete using level-order traversal
2. Find the rightmost node in the last level (this maintains the CBT property)
3. Replace the deleted node's value with the rightmost node's value
4. Remove the rightmost node from the last level

Let's see this in action with examples:

Example 1: Delete Node 3 (Rightmost in Last Level)

Before deletion:

Step 1: Find rightmost node in last level (node 20):

Step 2: Replace node 3's value with 20, then delete node 20:

Example 2: Delete Node 5 (Internal Node)

Before deletion:

Step 1: Find rightmost node in last level (node 20):

Step 2: Replace node 5's value with 20, then delete node 20:

Example 3: Delete Root Node (10)

Before deletion:

Step 1: Find rightmost node in last level (node 20):

Step 2: Replace root's value with 20, then delete node 20:

Key Point: This deletion strategy maintains the Complete Binary Tree property by always removing the rightmost node from the last level, ensuring the tree structure remains balanced and consistent with level-order insertion.

Traversal Operations

Traversal is the process of visiting all nodes in a tree. There are three main ways to traverse a Binary Tree, each with different visit orders.

In-Order Traversal (Left, Root, Right)

In in-order traversal, we visit the left subtree first, then the root, then the right subtree.

// InOrderTraversal performs in-order traversal (Left, Root, Right)
func (bt *BinaryTree) InOrderTraversal() []int {
    var result []int
    bt.inOrderRecursive(bt.Root, &result)
    return result
}

func (bt *BinaryTree) inOrderRecursive(node *Node, result *[]int) {
    if node == nil {
        return
    }
    bt.inOrderRecursive(node.Left, result)
    *result = append(*result, node.Value)
    bt.inOrderRecursive(node.Right, result)
}

Step-by-step visualization:

Result: [3, 5, 7, 10, 12, 15, 20]

Pre-Order Traversal (Root, Left, Right)

In pre-order traversal, we visit the root first, then the left subtree, then the right subtree.

// PreOrderTraversal performs pre-order traversal (Root, Left, Right)
func (bt *BinaryTree) PreOrderTraversal() []int {
    var result []int
    bt.preOrderRecursive(bt.Root, &result)
    return result
}

func (bt *BinaryTree) preOrderRecursive(node *Node, result *[]int) {
    if node == nil {
        return
    }
    *result = append(*result, node.Value)
    bt.preOrderRecursive(node.Left, result)
    bt.preOrderRecursive(node.Right, result)
}

Step-by-step visualization:

Visit order:

1. Visit 10 (root)
2. Go left, visit 5
3. Go left, visit 3
4. Back, go right, visit 7
5. Back to root, go right, visit 15
6. Go left, visit 12
7. Go right, visit 20

Result: [10, 5, 3, 7, 15, 12, 20]

Post-Order Traversal (Left, Right, Root)

In post-order traversal, we visit the left subtree first, then the right subtree, then the root.

// PostOrderTraversal performs post-order traversal (Left, Right, Root)
func (bt *BinaryTree) PostOrderTraversal() []int {
    var result []int
    bt.postOrderRecursive(bt.Root, &result)
    return result
}

func (bt *BinaryTree) postOrderRecursive(node *Node, result *[]int) {
    if node == nil {
        return
    }
    bt.postOrderRecursive(node.Left, result)
    bt.postOrderRecursive(node.Right, result)
    *result = append(*result, node.Value)
}

Step-by-step visualization:

Visit order:

1. Go to leftmost (3) → Visit 3
2. Back to 5, go right to 7 → Visit 7
3. Back to 5 → Visit 5
4. Back to 10, go right to 15, go left to 12 → Visit 12
5. Back to 15, go right to 20 → Visit 20
6. Back to 15 → Visit 15
7. Back to 10 → Visit 10

Result: [3, 7, 5, 12, 20, 15, 10]

Search Operation

Searching in a Binary Tree requires checking every node since there's no ordering guarantee. We'll use a recursive approach to search through the entire tree.

Search Implementation

// Search looks for a value in the tree
func (bt *BinaryTree) Search(value int) bool {
    return bt.searchRecursive(bt.Root, value)
}

func (bt *BinaryTree) searchRecursive(node *Node, value int) bool {
    if node == nil {
        return false
    }

    if node.Value == value {
        return true
    }

    // Search in left and right subtrees
    return bt.searchRecursive(node.Left, value) ||
           bt.searchRecursive(node.Right, value)
}

Step-by-Step Search Visualization

Let's search for value 7 in our tree:

Initial tree:

Search path:

The search starts at the root (10), checks the left subtree, finds 7 in the right child of node 5, and returns true.

Time Complexity

Let's analyze the time complexity of each operation:

Detailed Deletion Complexity Analysis

The deletion operation has O(n) time complexity, which can be broken down as follows:

1. Finding the node to delete: O(n)

   • Uses level-order traversal to find the target node
   • In worst case, we traverse all n nodes

2. Finding the rightmost node in the last level: O(n)

   • Performs a complete level-order traversal to find the rightmost node
   • Must visit all nodes to determine which is the rightmost in the last level

3. Replacing and removing: O(1)

   • Simple pointer operations

Total: O(n) + O(n) + O(1) = O(n)

Space Complexity:

• Insert: O(n) for the queue used in level-order traversal
• Delete: O(n) for the queue used in both finding the node and finding the rightmost node
• Search: O(h) where h is the height, due to recursive calls
• Traversal: O(h) where h is the height, due to recursive calls
  • In worst case (skewed tree): O(n)
  • In best case (balanced/complete tree): O(log n)

Note: Since we're maintaining a Complete Binary Tree structure, the height h is approximately log₂(n), making the space complexity for recursive operations O(log n) in the typical case.

Conclusion

In this guide, we've explored the Binary Tree data structure and its implementation in Go. We covered:

1. Basic Structure: Understanding nodes, root, leaves, and the tree hierarchy
2. Insert Operation: Level-order insertion that creates a Complete Binary Tree (CBT) with step-by-step visualization
3. Delete Operation: CBT-preserving deletion that replaces the deleted node with the rightmost node in the last level, maintaining the tree structure
4. Traversal Operations: Three different traversal methods (in-order, pre-order, post-order) with visit order visualization
5. Search Operation: Linear search through the entire tree
6. Complete Implementation: A working Go program demonstrating all operations

Key Implementation Details:

• Insert Strategy: Our level-order insertion always creates a Complete Binary Tree, where all levels are filled except possibly the last level, which is filled from left to right. This ensures a balanced structure.
• Delete Strategy: Unlike BST deletion, our deletion maintains the CBT property by replacing the deleted node with the rightmost node in the last level, then removing that rightmost node. This approach is specific to level-order binary trees and preserves the tree's structure.

Binary Trees are fundamental building blocks for more advanced data structures like Binary Search Trees, AVL Trees, and Red-Black Trees. Understanding Binary Trees is essential for solving many tree-related problems in computer science.

The key takeaway is that Binary Trees provide a flexible hierarchical structure, but without ordering rules, operations like search and delete require checking potentially all nodes, resulting in O(n) time complexity. For applications requiring efficient search, consider using a Binary Search Tree instead.

This post is written/assisted by AI, reviewed by human. Read more about it here.