- Software Letters
- Posts
- Mastering Data Structures with 50 Coding Challenges: Trees, Graphs, Stacks, and Queues - Part 1
Mastering Data Structures with 50 Coding Challenges: Trees, Graphs, Stacks, and Queues - Part 1
An In-Depth Guide to Essential Data Structures for Efficient Programming and Problem-Solving
Houssem BEN SLAMA
July 22, 2024 • Estimated Reading Time: 21 minutes
In computer science, understanding and effectively utilizing data structures is crucial for designing efficient algorithms and solving complex problems. Among the fundamental data structures are trees, graphs, stacks, and queues. Each of these structures serves unique purposes and has distinct characteristics that make them suitable for different types of applications and scenarios.
This guide delves into these essential data structures, providing clear definitions, characteristics, and practical examples in Go (Golang). By exploring trees, graphs, stacks, and queues, you'll gain a comprehensive understanding of their functionalities and how to implement them. Additionally, we've included 50 coding challenges designed to test and enhance your knowledge of these data structures. These challenges will enable you to improve your problem-solving skills and tackle a wide range of computational problems with confidence.
Arrays and Slices
1. Reverse Array/Slice
Explanation: Write a function that reverses an array or slice of integers. The function should take a slice of integers and reverse the order of elements in place.
Source Code:
package main
import (
"fmt"
)
func reverseArray(arr []int) {
left, right := 0, len(arr)-1
for left < right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
func main() {
arr := []int{1, 2, 3, 4, 5}
reverseArray(arr)
fmt.Println(arr) // Output: [5, 4, 3, 2, 1]
}2. Find Maximum
Explanation: Write a function to find the maximum element in an array or slice. The function should return the maximum value found.
Source Code:
package main
import (
"fmt"
)
func findMaximum(arr []int) int {
if len(arr) == 0 {
return 0 // or some indication that the array is empty
}
max := arr[0]
for _, value := range arr {
if value > max {
max = value
}
}
return max
}
func main() {
arr := []int{1, 2, 3, 4, 5}
max := findMaximum(arr)
fmt.Println(max) // Output: 5
}3. Rotate Array
Explanation: Write a function that rotates an array by a given number of steps. The function should take a slice of integers and rotate the elements to the right by the specified number of steps.
Source Code:
package main
import (
"fmt"
)
func rotateArray(arr []int, steps int) {
n := len(arr)
steps = steps % n
reverse := func(arr []int, start, end int) {
for start < end {
arr[start], arr[end] = arr[end], arr[start]
start++
end--
}
}
reverse(arr, 0, n-1)
reverse(arr, 0, steps-1)
reverse(arr, steps, n-1)
}
func main() {
arr := []int{1, 2, 3, 4, 5}
rotateArray(arr, 2)
fmt.Println(arr) // Output: [4, 5, 1, 2, 3]
}4. Merge Sorted Arrays
Explanation: Write a function that merges two sorted arrays into a single sorted array.
Source Code:
package main
import (
"fmt"
)
func mergeSortedArrays(arr1, arr2 []int) []int {
i, j := 0, 0
merged := make([]int, 0, len(arr1)+len(arr2))
for i < len(arr1) && j < len(arr2) {
if arr1[i] < arr2[j] {
merged = append(merged, arr1[i])
i++
} else {
merged = append(merged, arr2[j])
j++
}
}
merged = append(merged, arr1[i:]...)
merged = append(merged, arr2[j:]...)
return merged
}
func main() {
arr1 := []int{1, 3, 5}
arr2 := []int{2, 4, 6}
merged := mergeSortedArrays(arr1, arr2)
fmt.Println(merged) // Output: [1, 2, 3, 4, 5, 6]
}5. Remove Duplicates
Explanation: Write a function that removes duplicate elements from an array or slice.
Source Code:
package main
import (
"fmt"
)
func removeDuplicates(arr []int) []int {
elements := make(map[int]bool)
result := []int{}
for _, value := range arr {
if _, found := elements[value]; !found {
elements[value] = true
result = append(result, value)
}
}
return result
}
func main() {
arr := []int{1, 2, 2, 3, 4, 4, 5}
uniqueArr := removeDuplicates(arr)
fmt.Println(uniqueArr) // Output: [1, 2, 3, 4, 5]
}6. Pair Sum
Explanation: Write a function that finds all pairs of integers in an array that sum up to a given target.
Source Code:
package main
import (
"fmt"
)
func pairSum(arr []int, target int) [][2]int {
pairs := [][2]int{}
elements := make(map[int]bool)
for _, value := range arr {
complement := target - value
if elements[complement] {
pairs = append(pairs, [2]int{complement, value})
}
elements[value] = true
}
return pairs
}
func main() {
arr := []int{1, 2, 3, 4, 5}
target := 6
pairs := pairSum(arr, target)
fmt.Println(pairs) // Output: [[1 5] [2 4]]
}7. Subarray Sum
Explanation: Write a function to find the sum of all subarrays of a given array.
Source Code:
package main
import (
"fmt"
)
func subarraySum(arr []int) int {
totalSum := 0
n := len(arr)
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
for k := i; k <= j; k++ {
totalSum += arr[k]
}
}
}
return totalSum
}
func main() {
arr := []int{1, 2, 3}
sum := subarraySum(arr)
fmt.Println(sum) // Output: 20
}Linked Lists
A linked list is a linear data structure where each element, called a node, contains a data part and a reference (or link) to the next node in the sequence. Linked lists are used to efficiently insert and delete elements because these operations do not require shifting elements, as opposed to arrays.
Types of Linked Lists
Singly Linked List: Each node contains data and a reference to the next node.
Doubly Linked List: Each node contains data, a reference to the next node, and a reference to the previous node.
Circular Linked List: The last node points to the first node, making a circular structure. This can be applied to singly or doubly linked lists.
Characteristics
Dynamic Size: The size of a linked list can grow or shrink dynamically as nodes are added or removed.
Ease of Insertion/Deletion: Inserting or deleting a node does not require shifting elements; it only involves changing the references of the surrounding nodes.
Sequential Access: Unlike arrays, linked lists do not allow direct access to elements based on an index. Elements must be accessed sequentially starting from the head of the list.
Linked List Node Structure
Singly Linked List Node
In a singly linked list, each node has two parts:
Data: Stores the value.
Next: A reference to the next node in the list.
8. Reverse Linked List
Explanation: Write a function that reverses a singly linked list.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
fmt.Println()
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
printList(head) // Output: 1 2 3 4 5
reversedHead := reverseList(head)
printList(reversedHead) // Output: 5 4 3 2 1
}9. Detect Cycle
Explanation: Write a function to detect if a linked list has a cycle.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
func main() {
node1 := &ListNode{Val: 1}
node2 := &ListNode{Val: 2}
node3 := &ListNode{Val: 3}
node4 := &ListNode{Val: 4}
node5 := &ListNode{Val: 5}
node1.Next = node2
node2.Next = node3
node3.Next = node4
node4.Next = node5
node5.Next = node3 // Create a cycle
fmt.Println(hasCycle(node1)) // Output: true
}10. Merge Two Sorted Lists
Explanation: Write a function to merge two sorted linked lists.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
}
if l2 != nil {
current.Next = l2
}
return dummy.Next
}
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
fmt.Println()
}
func main() {
l1 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 5}}}
l2 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 6}}}
mergedList := mergeTwoLists(l1, l2)
printList(mergedList) // Output: 1 2 3 4 5 6
}11. Remove N-th Node
Explanation: Write a function to remove the N-th node from the end of a linked list.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
first, second := dummy, dummy
for i := 0; i <= n; i++ {
first = first.Next
}
for first != nil {
first = first.Next
second = second.Next
}
second.Next = second.Next.Next
return dummy.Next
}
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
fmt.Println()
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
printList(head) // Output: 1 2 3 4 5
updatedHead := removeNthFromEnd(head, 2)
printList(updatedHead) // Output: 1 2 3 5
}12. Middle of Linked List
Explanation: Write a function to find the middle node of a linked list.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
fmt.Println()
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
middle := middleNode(head)
fmt.Println(middle.Val) // Output: 3
}13. Palindrome Linked List
Explanation: Write a function to check if a linked list is a palindrome.
A palindrome is a sequence of characters that reads the same backward as forward. It can be a word, phrase, number, or any other sequence of characters. Examples of palindromic words include "madam," "racecar," and "level."
Characteristics of Palindromes
Symmetry: The most important characteristic of a palindrome is its symmetry. The characters at the beginning and end of the sequence mirror each other as you move towards the center.
Case Insensitivity: When considering whether a sequence is a palindrome, case is often ignored. For instance, "Madam" is considered a palindrome.
Ignoring Non-Alphanumeric Characters: In more flexible definitions, spaces, punctuation, and other non-alphanumeric characters are often ignored. For example, "A man, a plan, a canal: Panama" is considered a palindrome if you ignore spaces and punctuation.
Palindrome Check Algorithm
To determine if a string is a palindrome, follow these steps:
Normalize the String: Convert the string to a uniform case (usually lowercase) and remove any non-alphanumeric characters if necessary.
Compare Characters: Compare characters from the beginning and end of the string moving towards the center. If all corresponding characters are the same, the string is a palindrome.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
// Find the middle of the list
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// Reverse the second half of the list
var prev *ListNode
for slow != nil {
next := slow.Next
slow.Next = prev
prev = slow
slow = next
}
// Compare the first and second half
first, second := head, prev
for second != nil {
if first.Val != second.Val {
return false
}
first = first.Next
second = second.Next
}
return true
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 2, Next: &ListNode{Val: 1}}}}
fmt.Println(isPalindrome(head)) // Output: true
}14. Intersection of Two Linked Lists
Explanation: Write a function to find the intersection node of two singly linked lists.
Source Code:
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
lenA, lenB := 0, 0
tempA, tempB := headA, headB
for tempA != nil {
lenA++
tempA = tempA.Next
}
for tempB != nil {
lenB++
tempB = tempB.Next
}
tempA, tempB = headA, headB
if lenA > lenB {
for i := 0; i < lenA-lenB; i++ {
tempA = tempA.Next
}
} else {
for i := 0; i < lenB-lenA; i++ {
tempB = tempB.Next
}
}
for tempA != nil && tempB != nil {
if tempA == tempB {
return tempA
}
tempA = tempA.Next
tempB = tempB.Next
}
return nil
}
func main() {
common := &ListNode{Val: 8, Next: &ListNode{Val: 10}}
headA := &ListNode{Val: 3, Next: &ListNode{Val: 1, Next: common}}
headB := &ListNode{Val: 5, Next: common}
intersection := getIntersectionNode(headA, headB)
if intersection != nil {
fmt.Println(intersection.Val) // Output: 8
} else {
fmt.Println("No intersection")
}
}Stacks and Queues
Stacks and queues are fundamental data structures used in computer science to store and manage collections of elements. They follow specific principles for adding (pushing/enqueuing) and removing (popping/dequeuing) elements.
Stacks
Definition: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed.
Characteristics
LIFO Principle: The most recently added element is the first to be removed.
Push Operation: Adds an element to the top of the stack.
Pop Operation: Removes the element from the top of the stack.
Top Operation: Retrieves, but does not remove, the element at the top of the stack.
Example
Think of a stack of plates. You can only take the top plate off (pop) and add a plate on the top (push).
15. Implement Stack
Explanation: Implement a stack using slices. The stack should support push, pop, and top operations.
Source Code:
package main
import (
"fmt"
)
type Stack struct {
items []int
}
func (s *Stack) Push(val int) {
s.items = append(s.items, val)
}
func (s *Stack) Pop() int {
if len(s.items) == 0 {
return -1 // or some indication that the stack is empty
}
top := s.items[len(s.items)-1]
s.items = s.items[:len(s.items)-1]
return top
}
func (s *Stack) Top() int {
if len(s.items) == 0 {
return -1 // or some indication that the stack is empty
}
return s.items[len(s.items)-1]
}
func main() {
stack := &Stack{}
stack.Push(1)
stack.Push(2)
stack.Push(3)
fmt.Println(stack.Top()) // Output: 3
fmt.Println(stack.Pop()) // Output: 3
fmt.Println(stack.Top()) // Output: 2
}16. Implement Queue
Explanation: Implement a queue using slices. The queue should support enqueue, dequeue, and front operations.
Source Code:
package main
import (
"fmt"
)
type Queue struct {
items []int
}
func (q *Queue) Enqueue(val int) {
q.items = append(q.items, val)
}
func (q *Queue) Dequeue() int {
if len(q.items) == 0 {
return -1 // or some indication that the queue is empty
}
front := q.items[0]
q.items = q.items[1:]
return front
}
func (q *Queue) Front() int {
if len(q.items) == 0 {
return -1 // or some indication that the queue is empty
}
return q.items[0]
}
func main() {
queue := &Queue{}
queue.Enqueue(1)
queue.Enqueue(2)
queue.Enqueue(3)
fmt.Println(queue.Front()) // Output: 1
fmt.Println(queue.Dequeue()) // Output: 1
fmt.Println(queue.Front()) // Output: 2
}17. Valid Parentheses
Explanation: Write a function to check if a string of parentheses is valid. A string is valid if every opening parenthesis has a corresponding closing parenthesis in the correct order.
Source Code:
package main
import (
"fmt"
)
func isValidParentheses(s string) bool {
stack := []rune{}
pair := map[rune]rune{')': '(', '}': '{', ']': '['}
for _, char := range s {
switch char {
case '(', '{', '[':
stack = append(stack, char)
case ')', '}', ']':
if len(stack) == 0 || stack[len(stack)-1] != pair[char] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
func main() {
s := "()[]{})"
fmt.Println(isValidParentheses(s)) // Output: false
}18. Min Stack
Explanation: Implement a stack that supports push, pop, and retrieving the minimum element in constant time.
Source Code:
package main
import (
"fmt"
)
type MinStack struct {
stack []int
minStack []int
}
func (ms *MinStack) Push(val int) {
ms.stack = append(ms.stack, val)
if len(ms.minStack) == 0 || val <= ms.minStack[len(ms.minStack)-1] {
ms.minStack = append(ms.minStack, val)
}
}
func (ms *MinStack) Pop() {
if len(ms.stack) == 0 {
return
}
top := ms.stack[len(ms.stack)-1]
ms.stack = ms.stack[:len(ms.stack)-1]
if top == ms.minStack[len(ms.minStack)-1] {
ms.minStack = ms.minStack[:len(ms.minStack)-1]
}
}
func (ms *MinStack) Top() int {
if len(ms.stack) == 0 {
return -1 // or some indication that the stack is empty
}
return ms.stack[len(ms.stack)-1]
}
func (ms *MinStack) GetMin() int {
if len(ms.minStack) == 0 {
return -1 // or some indication that the stack is empty
}
return ms.minStack[len(ms.minStack)-1]
}
func main() {
ms := &MinStack{}
ms.Push(3)
ms.Push(5)
fmt.Println(ms.GetMin()) // Output: 3
ms.Push(2)
ms.Push(1)
fmt.Println(ms.GetMin()) // Output: 1
ms.Pop()
fmt.Println(ms.GetMin()) // Output: 2
}19. Daily Temperatures
Explanation: Write a function that takes an array of daily temperatures and returns an array of how many days you would have to wait for a warmer temperature.
Source Code:
package main
import (
"fmt"
)
func dailyTemperatures(T []int) []int {
n := len(T)
result := make([]int, n)
stack := []int{}
for i := n - 1; i >= 0; i-- {
for len(stack) > 0 && T[i] >= T[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
result[i] = 0
} else {
result[i] = stack[len(stack)-1] - i
}
stack = append(stack, i)
}
return result
}
func main() {
temperatures := []int{73, 74, 75, 71, 69, 72, 76, 73}
fmt.Println(dailyTemperatures(temperatures)) // Output: [1 1 4 2 1 1 0 0]
}20. Circular Queue
Explanation: Implement a circular queue. The queue should support enqueue, dequeue, front, and rear operations.
Source Code:
package main
import (
"fmt"
)
type CircularQueue struct {
items []int
front int
rear int
size int
}
func NewCircularQueue(k int) *CircularQueue {
return &CircularQueue{
items: make([]int, k),
front: -1,
rear: -1,
size: k,
}
}
func (q *CircularQueue) EnQueue(val int) bool {
if (q.rear+1)%q.size == q.front {
return false // Queue is full
}
if q.front == -1 {
q.front = 0
}
q.rear = (q.rear + 1) % q.size
q.items[q.rear] = val
return true
}
func (q *CircularQueue) DeQueue() bool {
if q.front == -1 {
return false // Queue is empty
}
if q.front == q.rear {
q.front = -1
q.rear = -1
} else {
q.front = (q.front + 1) % q.size
}
return true
}
func (q *CircularQueue) Front() int {
if q.front == -1 {
return -1 // Queue is empty
}
return q.items[q.front]
}
func (q *CircularQueue) Rear() int {
if q.rear == -1 {
return -1 // Queue is empty
}
return q.items[q.rear]
}
func main() {
cq := NewCircularQueue(3)
fmt.Println(cq.EnQueue(1)) // Output: true
fmt.Println(cq.EnQueue(2)) // Output: true
fmt.Println(cq.EnQueue(3)) // Output: true
fmt.Println(cq.EnQueue(4)) // Output: false (Queue is full)
fmt.Println(cq.Rear()) // Output: 3
fmt.Println(cq.DeQueue()) // Output: true
fmt.Println(cq.Front()) // Output: 2
}21. Queue using Stacks
Explanation: Implement a queue using two stacks.
Source Code:
package main
import (
"fmt"
)
type MyQueue struct {
stack1 []int
stack2 []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.stack1 = append(q.stack1, x)
}
func (q *MyQueue) Pop() int {
if len(q.stack2) == 0 {
for len(q.stack1) > 0 {
q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
q.stack1 = q.stack1[:len(q.stack1)-1]
}
}
top := q.stack2[len(q.stack2)-1]
q.stack2 = q.stack2[:len(q.stack2)-1]
return top
}
func (q *MyQueue) Peek() int {
if len(q.stack2) == 0 {
for len(q.stack1) > 0 {
q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
q.stack1 = q.stack1[:len(q.stack1)-1]
}
}
return q.stack2[len(q.stack2)-1]
}
func (q *MyQueue) Empty() bool {
return len(q.stack1) == 0 && len(q.stack2) == 0
}
func main() {
queue := Constructor()
queue.Push(1)
queue.Push(2)
fmt.Println(queue.Peek()) // Output: 1
fmt.Println(queue.Pop()) // Output: 1
fmt.Println(queue.Empty()) // Output: false
}Trees and Graphs
Trees
Definition: A tree is a hierarchical data structure that consists of nodes, with a single node called the root, from which other nodes branch out. Each node contains a value and references to its children nodes.
Characteristics
Root Node: The topmost node in the tree.
Parent and Child: Each node in a tree has a parent node (except the root) and zero or more child nodes.
Leaf Nodes: Nodes with no children.
Subtree: Any node and its descendants form a subtree.
Height: The length of the longest path from the root to a leaf.
Depth: The length of the path from the root to a node.
Types of Trees
Binary Tree: Each node has at most two children, often referred to as the left and right child.
Binary Search Tree (BST): A binary tree with the property that the value of each node is greater than the values of all nodes in its left subtree and less than the values of all nodes in its right subtree.
AVL Tree: A self-balancing binary search tree where the difference between the heights of left and right subtrees cannot be more than one.
Red-Black Tree: A self-balancing binary search tree with an additional bit of storage per node to denote the color of the node, ensuring the tree remains balanced.
Graphs
Definition: A graph is a collection of nodes, called vertices, and edges that connect pairs of vertices. Graphs can represent various real-world systems like social networks, transportation networks, and more.
Characteristics
Vertices (Nodes): The fundamental units of the graph.
Edges (Links): The connections between the vertices.
Directed Graph: Edges have a direction, going from one vertex to another.
Undirected Graph: Edges have no direction, simply connecting two vertices.
Weighted Graph: Edges have weights representing the cost or distance between vertices.
Unweighted Graph: Edges do not have weights.
Adjacency List: A representation where each vertex stores a list of adjacent vertices.
Adjacency Matrix: A 2D array representation where each cell (i, j) indicates the presence or absence of an edge between vertices i and j.
22. Binary Tree Inorder Traversal
Explanation: Write a function to perform inorder traversal of a binary tree.
Source Code:
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
result := []int{}
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
result = append(result, node.Val)
inorder(node.Right)
}
inorder(root)
return result
}
func main() {
root := &TreeNode{Val: 1, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
fmt.Println(inorderTraversal(root)) // Output: [1 3 2]
}23. Binary Tree Level Order Traversal
Explanation: Write a function to perform level order traversal of a binary tree.
Source Code:
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func levelOrderTraversal(root *TreeNode) [][]int {
result := [][]int{}
if root == nil {
return result
}
queue := []*TreeNode{root}
for len(queue) > 0 {
level := []int{}
n := len(queue)
for i := 0; i < n; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
func main() {
root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Right: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 3}}
fmt.Println(levelOrderTraversal(root)) // Output: [[1] [2 3] [4]]
}24. Binary Search Tree (BST) Insertion
Explanation: Write a function to insert a node in a BST.
Source Code:
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
if val < root.Val {
root.Left = insertIntoBST(root.Left, val)
} else {
root.Right = insertIntoBST(root.Right, val)
}
return root
}
func inorderTraversal(root *TreeNode) []int {
result := []int{}
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
result = append(result, node.Val)
inorder(node.Right)
}
inorder(root)
return result
}
func main() {
root := &TreeNode{Val: 4, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 1}, Right: &TreeNode{Val: 3}}, Right: &TreeNode{Val: 7}}
root = insertIntoBST(root, 5)
fmt.Println(inorderTraversal(root)) // Output: [1 2 3 4 5 7]
}25. Lowest Common Ancestor
Explanation: Write a function to find the lowest common ancestor of two nodes in a binary tree.
Source Code:
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left == nil {
return right
}
return left
}
func main() {
root := &TreeNode{Val: 3, Left: &TreeNode{Val: 5, Left: &TreeNode{Val: 6}, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 7}, Right: &TreeNode{Val: 4}}}, Right: &TreeNode{Val: 1, Left: &TreeNode{Val: 0}, Right: &TreeNode{Val: 8}}}
p := root.Left // Node with value 5
q := root.Left.Right.Right // Node with value 4
ancestor := lowestCommonAncestor(root, p, q)
fmt.Println(ancestor.Val) // Output: 5
}