Trees

A tree is a hierarchical, dynamic data structure that consists of nodes, where each node contains a value and a list of references to other nodes (its children). The top node of the tree is called the root, and nodes with no children are called leaves. Each node is connected to its children in a way that no cycles are formed, meaning there is exactly one path from the root to any node. Trees are used to represent and manage hierarchical data, such as file systems, organizational structures, and various algorithms like decision trees.

Here we will be focusing on binary trees for simplicity, but there are other types of trees.

Overview of Trees

1. Structure: A tree consists of nodes connected by edges, with one node designated as the root. Each node has zero or more child nodes.

2. Types of Binary Trees:

• Binary Search Tree (BST): A binary tree where the left subtree contains only nodes with values less than the parent node, and the right subtree only nodes with values greater.

graph TD;
    A[8] --> B[3]
    A --> C[10]
    B --> D[1]
    B --> E[6]
    E --> F[4]
    E --> G[7]
    C --> H[14]
    H --> I[13]

• Balanced Tree: AVL trees and Red-Black trees are examples of self-balancing binary search trees.

graph TD;
    A[8] --> B[4]
    A --> C[12]
    B --> D[2]
    B --> E[6]
    C --> F[10]
    C --> G[14]

• Complete Binary Tree: Every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

graph TD;
    A[1] --> B[2]
    A --> C[3]
    B --> D[4]
    B --> E[5]
    C --> F[6]
    C --> G[7]

4. Properties: The height of a tree is a critical factor in many operations, influencing their time complexity.

Common Operations and Their Big O Notation

Advantages

• Hierarchical Organization: Efficiently represents hierarchical data, mimicking real-world structures.
• Quick Operations: Offers O(log n) time complexity for search, insertion, and deletion in balanced trees.
• Versatile Use: Fundamental in implementing heaps, graphs, and indexing in databases.
• Efficient Data Management: Facilitates efficient organization, retrieval, and management of data.

Disadvantages

• Performance Degradation: Unbalanced trees can lead to O(n) time complexity, similar to a linked list, losing binary search advantages.

graph LR
    A[1] --> B[2]
    B --> C[3]
    C --> D[4]
    D --> E[5]
    E --> F[6]

• Rebalancing Overhead: Maintaining balance in trees (e.g., AVL, Red-Black) adds complexity and performance costs.
• Increased Memory Usage: Requires extra memory for pointers to child nodes.
• Recursive Algorithm Issues: Deep trees can cause stack overflow problems with recursive algorithms.

Code representation

// TreeNode represents a node in a binary tree.
type TreeNode struct {
	Data  int
	Left  *TreeNode
	Right *TreeNode
}

// BinaryTree represents a binary tree.
type BinaryTree struct {
	Root *TreeNode
}

// NewBinaryTree creates a new empty binary tree.
func NewBinaryTree() *BinaryTree {
	return &BinaryTree{}
}

// Insert adds a new node with the given data to the binary tree.
func (bt *BinaryTree) Insert(data int) {
	newNode := &TreeNode{Data: data, Left: nil, Right: nil}
	if bt.Root == nil {
		bt.Root = newNode
	} else {
		insertNode(bt.Root, newNode)
	}
}

// Helper function to recursively insert a node into the binary tree.
func insertNode(node, newNode *TreeNode) {
	if newNode.Data < node.Data {
		if node.Left == nil {
			node.Left = newNode
		} else {
			insertNode(node.Left, newNode)
		}
	} else {
		if node.Right == nil {
			node.Right = newNode
		} else {
			insertNode(node.Right, newNode)
		}
	}
}

// InOrderTraversal performs an in-order traversal of the binary tree and returns the elements.
func (bt *BinaryTree) InOrderTraversal() []int {
	result := []int{}
	inOrder(bt.Root, &result)
	return result
}

// Helper function to perform in-order traversal.
func inOrder(node *TreeNode, result *[]int) {
	if node != nil {
		inOrder(node.Left, result)
		*result = append(*result, node.Data)
		inOrder(node.Right, result)
	}
}