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

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

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 RedBlack trees are examples of selfbalancing 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]
 Properties: The height of a tree is a critical factor in many operations, influencing their time complexity.
Common Operations and Their Big O Notation
Operation  Time Complexity (Average)  Time Complexity (Worst)  Comments 

Insert  O(log n)  O(n)  In a balanced BST, insertion is O(log n), but can degrade to O(n) in an unbalanced tree. 
Search  O(log n)  O(n)  Similar to insertion, depends on the tree’s balance. 
Delete  O(log n)  O(n)  Deletion might require tree rebalancing in BSTs. 
Traverse  O(n)  O(n)  Traversal operations (inorder, preorder, postorder) visit all nodes. 
Find Min/Max  O(log n)  O(n)  In BSTs, the min/max values are in the leftmost/rightmost nodes. 
Advantages
 Hierarchical Organization: Efficiently represents hierarchical data, mimicking realworld 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, RedBlack) 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 inorder 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 inorder traversal.
func inOrder(node *TreeNode, result *[]int) {
if node != nil {
inOrder(node.Left, result)
*result = append(*result, node.Data)
inOrder(node.Right, result)
}
}